Gibt es nicht konstruktive Existenznachweise für „kleine“ Turingmaschinen / NFAs?

Nachdem ich eine verwandte Frage über nichtkonstruktive Existenzbeweise von Algorithmen gelesen hatte , fragte ich mich, ob es Methoden gibt, um die Existenz von "kleinen" (etwa zustandsbezogenen) Rechenmaschinen zu zeigen, ohne sie tatsächlich zu erstellen.

Formal:

Nehmen wir an, wir erhalten eine Sprache und korrigieren ein Rechenmodell (NFAs / Turing Machine / etc.).$L\subseteq \Sigma^*$

Gibt es nicht konstruktive Existenzergebnisse, die zeigen, dass eine Zustandsmaschine für L existiert, aber ohne die Fähigkeit, sie zu finden (in p o l y ( n , | Σ | ) Zeit)?$n$$L$$poly(n,|\Sigma|)$

Zum Beispiel gibt es eine reguläre Sprache für die wir zeigen n s c ( L ) ≤ n , aber wir wissen nicht , wie ein bauen n -state Automaten für?$L$$nsc(L)\leq n$$n$

( ist die nicht-deterministische Zustand Komplexität des L , dh die Anzahl von Zuständen in dem minimal NFA die nimmt L ).$nsc(L)$$L$$L$

EDIT: Nach einigen Diskussionen mit Marzio (danke!) Ich denke, ich kann die Frage besser wie folgt formulieren:

Gibt es eine Sprache und ein Rechenmodell, für die Folgendes gilt:$L$

1. Wir wissen, wie man eine Maschine baut, die mit m Zuständen berechnet .$L$$m$

2. Wir haben einen Beweis dafür , dass -Zustände Maschine für L vorhanden ist (wobei n < < m ), aber entweder wir können es überhaupt nicht finden oder es würde nehmen exponentielle Zeit , es zu berechnen.$n$$L$$n << m$

Nur ein erweiterter Kommentar mit einem trivialen Beispiel; Sie können die Ein-Element-Sprache auswählen:

$L_k$$k$$k$

$k$$L_k$$\leq 2*k(\log k+2)$

$\mathtt{MOD_p} = \{a^{ip} \mid i \geq 0\}$$p$$O(\log p)$

$O(\log^{2+o(1)}p)$$\mathtt{MOD_p}$

REF: Abschnitt 4.2 von (Ambainis und Yakaryilmaz, 2015) .

Eine andere Lösung besteht darin, Higmans Lemma zu verwenden :

Eine unter Unterwörtern geschlossene Sprache ist regulär.

$u$$v$$u$$v$

Nehmen Sie also eine Sprache L, deren Unterwortabschluss regelmäßig ist, aber überhaupt nicht konstruierbar ist, da L willkürlich ist.