¿Se puede determinar si el lenguaje L se encuentra en NP?

Dado un lenguaje L definido por una máquina de Turing que lo decide, ¿es posible determinar algorítmicamente si L se encuentra en NP?

No. Primero, según el Teorema de Rice, esta es una propiedad de TM que depende solo del lenguaje que computan, por lo que no puede ser computable.

Pero, más que eso, se sabe que el conjunto de índices de (es decir, el conjunto de TM que calculan idiomas en N P ) es Σ 0 3 -completo ( Σ 0 3 en la jerarquía aritmética de computabilidad, no el jerarquía polinómica).$NP$$NP$$\Sigma^0_3$$\Sigma^0_3$

Preguntas como esta fueron investigadas por primera vez por Hajek . Para obtener más información, consulte, por ejemplo, este artículo de Ken Regan.

Algunas pepitas más del periódico de Hajek:

• El conjunto de índices de es Σ 0 3 -completo.$P$$\Sigma^0_3$
• es Π 0 2 -completo$\{i : P^{L(M_i)} \neq NP^{L(M_i)}\}$$\Pi^0_2$
• Hay una máquina de Turing total (se detiene en todas las entradas) tal que P L i = N P L i pero la declaración " P L i = N P L i " es independiente (donde L i = L ( M i ) ) . Del mismo modo para relativizaciones donde P ≠ N P .$M_i$$P^{L_i} = NP^{L_i}$$P^{L_i} = NP^{L_i}$$L_i = L(M_i)$$P \neq NP$

La respuesta a su pregunta literal es no, como señaló Joshua Grochow.

Sin embargo, como dijo Holger, es posible verificar en tiempo lineal si la máquina de Turing no determinista "se cronometra" y se detiene después de n ^ k pasos para alguna constante k, a través de alguna forma estándar de simulación de un reloj (como el código a continuación). A menudo, cuando un artículo o libro sugiere (incorrectamente) que es posible determinar si un NTM es tiempo polinómico, esto es lo que realmente significan. ¿Quizás es por eso que hiciste la pregunta? (Tuve la misma pregunta cuando aprendí por primera vez la teoría de la complejidad y en algún lugar vi la afirmación de que es posible verificar si un TM es poli-tiempo). La verdadera pregunta es por qué uno podría desear hacer esto, lo que discuto a continuación después de explicar como .

Hay muchas formas de agregar dicha función de reloj. Por ejemplo, imagine en la entrada x de longitud n, ejecutando alternativamente una declaración del "algoritmo primario" que se está sincronizando, y luego una declaración del siguiente algoritmo, que termina en (algo cercano a) n ^ k pasos:

para i_1 = 1 a n
  para i_2 = 1 a n
...
        para i_k = 1 a n
          no-op;
regreso;

Si el código anterior regresa antes de que el algoritmo primario se detenga, entonces detenga todo el cómputo (digamos, con rechazo).

El algoritmo que decide si una NTM es de esta forma, si se interpreta como un intento de un algoritmo para decidir si su entrada es una NTM de tiempo múltiple, informará algunos falsos negativos: se garantiza que algunas NTM se detendrán en tiempo polinómico, aunque no alternan la ejecución de una declaración de un algoritmo con una declaración de un reloj como el código anterior (por lo tanto, sería rechazado a pesar de ser poli-tiempo).

Pero no hay falsos positivos. Si un NTM pasa la prueba, definitivamente se detiene en el tiempo polinómico, por lo tanto, define un lenguaje NP. Sin embargo, quizás el comportamiento de su algoritmo primario subyacente se altera si el reloj a veces se agota antes de que el algoritmo primario se detenga, lo que hace que el cálculo se rechace aunque el algoritmo primario haya aceptado si se le hubiera dado suficiente tiempo para terminar. Por lo tanto, el lenguaje decidido puede ser diferente al del algoritmo primario. Pero, y esta es la clave, si el algoritmo principal que se está ejecutando es, de hecho, un algoritmo de tiempo polinómico que se ejecuta en el tiempo p (n), y si la constante k en el reloj es lo suficientemente grande como para que n ^ k> p (n), entonces el algoritmo primario siempre se detendrá antes de que se agote el reloj. En este caso, la respuesta del algoritmo primario no se altera, por lo que el algoritmo primario y la NTM sincronizada que lo simulan deciden el mismo lenguaje NP.

¿Porque es esto importante? Esto significa que es posible "enumerar todos los lenguajes NP" (lo cual, como dije en la literatura, a menudo es inexacto, como "decidir si una NTM dada es poli-tiempo" o "enumerar todas las NTM poli-tiempo"). Más precisamente, es posible enumerar una lista infinita de NTM M_1 M_2, ..., con las propiedades que

1. Cada M_k se ejecuta en tiempo polinómico (por ejemplo, al adjuntar un reloj ^ k-time a M_k), por lo tanto, decide un lenguaje NP y
2. Cada idioma NP es el idioma decidido por algunos M_i en la lista.

Lo que no sucede es que cada NTM de tiempo polinómico está en la lista. Pero cada lenguaje NP tiene un número infinito de NTM que lo representan. Por lo tanto, se garantiza que cada lenguaje NP tenga al menos algunos de sus NTM representativos en la lista, específicamente todos esos NTM en un índice k lo suficientemente grande que n ^ k excede el tiempo de ejecución de M_k.

Esto es útil para hacer trucos como la diagonalización, que requieren enumerar algorítmicamente tales listas infinitas (o ilimitadas) de todos los lenguajes NP. Y, por supuesto, toda esta discusión se aplica a muchos otros tipos de máquinas además de las NTM de poli-tiempo, como las TM deterministas de poli-tiempo.

$p(n)$