¿Existen pruebas no constructivas de la existencia de máquinas de Turing / NFA "pequeñas"?

Después de leer una pregunta relacionada , acerca de las pruebas de algoritmos de existencia no constructivas, me preguntaba si existen métodos para mostrar la existencia de máquinas de cómputo "pequeñas" (por ejemplo, a nivel de estado) sin construirlas realmente.

Formalmente:

supongamos que tenemos un lenguaje y arreglamos un modelo de cálculo (NFA / máquina de turing / etc.).$L\subseteq \Sigma^*$

¿Hay resultados de existencia no constructivos que muestren que existe una máquina de estados para L , pero sin la capacidad de encontrarla (en p o l y ( n , | Σ | ) tiempo)?$n$$L$$poly(n,|\Sigma|)$

Por ejemplo, ¿hay algún lenguaje regular para el que podamos mostrar n s c ( L ) ≤ n pero no sabemos cómo construir un autómata n- state?$L$$nsc(L)\leq n$$n$

( es la complejidad de estado no determinista de L , es decir, el número de estados en el NFA mínimo que acepta L ).$nsc(L)$$L$$L$

EDITAR: después de una discusión con Marzio (¡gracias!) Creo que puedo formular mejor la pregunta de la siguiente manera:

¿Existe un lenguaje y un modelo de cálculo para el que se cumple lo siguiente:$L$

1. Sabemos cómo construir una máquina que calcule que tiene m estados.$L$$m$

2. Tenemos una prueba de que máquina -Estados de L existe (en el que n < < m ), pero o bien no podemos encontrar en todo o que tomaría un tiempo exponencial para calcularla.$n$$L$$n << m$

Solo un comentario extendido con un ejemplo trivial; puedes elegir el idioma de un elemento:

$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: Sección 4.2 de (Ambainis y Yakaryilmaz, 2015) .

Otra solución es usar el lema de Higman :

Un lenguaje cerrado bajo subpalabras es regular.

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

Por lo tanto, tome cualquier lenguaje L, el cierre de su subpágina es regular pero no es en absoluto constructivo ya que L es arbitrario.