¿Por qué no es este problema indecidible en NP?

Claramente no hay ningún problema indecidible en NP. Sin embargo, según Wikipedia :

NP es el conjunto de todos los problemas de decisión para los cuales las instancias donde la respuesta es "sí" tienen [... pruebas que son] verificables en tiempo polinómico por una máquina de Turing determinista.

[...]

Se dice que un problema está en NP si y solo si existe un verificador para el problema que se ejecuta en tiempo polinómico.

Ahora considere el siguiente problema:

Dada una ecuación de diofantina , ¿tiene alguna solución entera?

Dada una solución, es fácil verificar en tiempo polinómico que realmente es una solución: simplemente inserte los números en la ecuación. Por lo tanto, el problema está en NP. Sin embargo, ¡ se sabe que resolver este problema es indecidible !

(De manera similar, parece que el problema de detención debería estar en NP, ya que la solución "sí" de "este programa se detiene en el N-ésimo paso" se puede verificar en N pasos).

Obviamente hay algo mal con mi comprensión, pero ¿qué es?

Una definición equivalente de NP es que consiste en todos los problemas que son decidibles (no solo verificables) en tiempo polinómico por una máquina de Turing no determinista. Se sabe que las NTM no son más poderosas que las TM en el sentido de que el conjunto de problemas que pueden decidir las NTM es idéntico al conjunto de problemas que pueden decidir las TM, por lo que, claramente, según esta definición, no puede haber problemas indecidibles en NP.

Para demostrar que las dos definiciones de NP son equivalentes, dada la existencia de un verificador determinista, puede demostrar que existe un decisor no determinista, y viceversa.

Digamos que tiene un verificador polinomial determinista. Luego también hay una máquina que adivina de forma no determinista un certificado de una longitud limitada por el polinomio correspondiente al límite de tamaño del certificado de este problema / verificador y luego ejecuta el verificador. Dado que el alfabeto es finito, el certificado para cualquier entrada dada es finito (y como máximo polinomial en el tamaño de la entrada), y el verificador se ejecuta en tiempo polinómico, la máquina se detiene en todas las ramas para todas las entradas y se ejecuta en (no determinista) tiempo polinomial. Por lo tanto, hay un decisor no determinista para cada verificador determinista.

Si tiene un decisor no determinista, entonces, para cada cálculo de aceptación, puede escribir la ruta de las elecciones tomadas por el decisor para alcanzar el estado de aceptación. Como el decisor se ejecuta en tiempo polinómico, esta ruta tendrá una longitud de polinomio como máximo. Y es fácil para una TM determinista validar que dicha ruta es una ruta válida a través de una NTM a un estado de aceptación, por lo que dichas rutas forman certificados para un verificador de tiempo polinómico para el problema. Por lo tanto, hay un verificador determinista para cada decisor no determinista.

Por lo tanto, cualquier problema indecidible no puede tener un verificador que funcione en certificados de tamaño polinómico (de lo contrario, la existencia del verificador implicaría la existencia de un decisor).

Cuando afirma que existe un verificador para el problema de detención, el certificado del que está hablando es una codificación de (TM, I, N), donde TM se detiene en la entrada I en N pasos. De hecho, esto se puede verificar en N pasos, pero el tamaño del certificado no es polinómico en el tamaño de la entrada (TM, I) al problema original (el problema de detención); N puede ser arbitrariamente grande (independientemente de la codificación). Si intenta convertir dicho verificador en un decisor no determinista, terminará con una máquina algo interesante. Debería poder probar eso cuando se ejecuta en (TM, I) para una TM que nodetener en la entrada I, no existen rutas que no se detengan a través de la máquina, pero también que para cualquier ruta que conduzca a un estado de detención siempre hay otra ruta más larga (correspondiente a una suposición de un N más grande), y por lo tanto no hay límite finito en Su tiempo de ejecución. Esencialmente esto se debe a que hay un espacio infinito que necesita ser explorado por la suposición inicial no determinista. La conversión de una NTM de este tipo en una TM determinista conduce a una de esas máquinas que no realiza bucles ni se detiene en alguna entrada. De hecho, no existe una NTM que pueda decidir el problema de detención, por lo que no existe un verificador que funcione en certificados con un tamaño acotado.

No estoy tan familiarizado con las ecuaciones de Diophantine, pero parece que esencialmente el mismo problema se aplica a su argumento allí.

Por esta razón, me resulta más fácil razonar sobre la definición NTM de NP. Hay verificadores para problemas que son indecidibles (solo que no funcionan para los certificados que tienen un tamaño polinómico limitado en el tamaño de la entrada al problema original). De hecho, cualquier TM que reconozca pero no decida algún idioma puede convertirse fácilmente en un verificador para el mismo idioma.

Si piensa en los verificadores, supongo que tiene que dar sus límites de tiempo en términos del tamaño de la entrada del problema original , no en términos del tamaño del certificado; puede inflar arbitrariamente el tamaño de los certificados para que el verificador se ejecute en un límite de tiempo inferior en términos del tamaño del certificado.

Creo que entendiste mal lo que significa resolver una ecuación de diofantina y el teorema de indecidibilidad de Matiyasevich .

Matiyasevich demostró que para cada conjunto RE hay una ecuación diofentina tal que solo si existen coeficientes enteros , .., tal que . En particular, el problema de detención es un conjunto típico de RE, por lo que resolver el problema anterior es indecidible.$S$$f(n;x_1,...,x_k)$$n \in S$$x_1$$x_k$$f(n;x_1,...,x_k) = 0$

Tenga en cuenta que no tienen un tamaño limitado y, en general, pueden ser arbitrariamente grandes, por lo que no hay un "certificado de tamaño polinómico" evidente en este problema.$x_1, ... x_k$

Para expandir: los enteros deben escribirse en binario para ser un certificado. Dado que estos enteros pueden ser arbitrariamente grandes (independientemente de ), tenemos que el certificado no es polinomial en o, lo que es más importante, no está limitado por una función computable.$x_1, ... , x_k$$n$$\log n$

Sin embargo, cada problema en tiene un certificado limitado por algún polinomio (donde es el tamaño de la entrada). Entonces, las preguntas son decididamente triviales, ya que puede enumerar todas las cadenas de bits posibles hasta la longitud y, si ninguna de ellas certifica la entrada, devuelve falso. Si alguno lo hace, devuelve verdadero. p ( N ) N N P p ( N $\mathsf{NP}$$p(N)$$N$$\mathsf{NP}$$p(N)$

Debería haber bajado a la definición formal :

$L$$p$$q$$M$

• $x$$M$$p(|x|)$$(x,y)$
• $x \in L$$y$$q(|x|)$$M(x,y) = 1$
• $x \not\in L$$y$$q(|x|)$$M(x,y) = 0$

Es decir, un verificador tiene que funcionar también en no soluciones. En algún lugar, los problemas indecidibles fallan (en su caso, la restricción de longitud de los candidatos a la solución probablemente no se cumple), como es obvio por la definición más clara (en el sentido de computabilidad) :

NP es el conjunto de problemas de decisión que puede decidir una máquina de Turing no determinista que se ejecuta en tiempo polinómico.

Intento proporcionar más detalles para mi respuesta anterior.

De hecho, esta pregunta es un problema de dilema.

Por un lado, el problema de la ecuación de diofantina (DEP) es indecidible según el teorema de Matiyesevich (el teorema de Matiyesevich responde al décimo problema de Hilbert, y el problema de detención de Turing responde a la generalización del décimo problema de Hilbert, es decir, el problema Entscheidungsproblem); pero, por otro lado, no hay ningún problema indecidible en NP según la definición de NP (decidible y verificable).

Es decir, DEP no está en NP o DEP está en NP. Ambos se refieren a la definición de NP.

Si DEP no está en NP, eso significa que los problemas en NP (NDTM Machine Máquina de Turing no determinada) son decidibles y verificables, es decir, aceptamos P = NP (NDTM).

Si DEP está en NP, entonces NP (NTM ＝ Non Turing Machine) contiene decidible e indecidible, obviamente decidible es verificable, por lo tanto, el problema es si indecidible es verificable. De hecho, ese es el famoso problema de P vs. NP. Ciertamente, indecidible no es verificable, por lo que NP corresponde a NTM (Máquina sin Turing) en lugar de NDTM (Máquina sin determinar de Turing).

Partiendo de la premisa de DEP está en NP (NTM), creemos que NP (NTM) es un problema no determinista (indecidible), y la definición actual de NP (NDTM, decidible y verificable) ha perdido este no determinismo (indecidible), por lo que creemos que necesita ser cuestionado.

Creemos que el dilema que planteó sobre la ecuación de diofantina es muy significativo, porque revela algo anormal en la definición actual de NP: - Se dice que un problema está en NP si y solo si existe un verificador para el problema que se ejecuta en polinomio hora.

Con respecto a la definición de NP, se puede rastrear hasta los años 60, donde se descubrió una gran cantidad de problemas aplicables y significativos para los cuales no se pudieron encontrar algoritmos polinomiales para resolverlos, a fin de reconocer estos problemas de aquellos problemas que se pueden resolver en el tiempo polinómico. (P), se expuso el concepto de NP.

Sin embargo, la definición actual de NP definida como verificable en tiempo polinómico confunde NP con P, porque un problema en P también es verificable en tiempo polinomial. En otras palabras, tal definición conduce a la pérdida de la esencia de NP, «no determinismo». En consecuencia, causa serias ambigüedades en la comprensión de NP, por ejemplo, su dilema: por naturaleza, el problema de la ecuación de diofantina es indecidible; pero por la definición de NP, es decidible, ...

En nuestra opinión, la dificultad para resolver «P versus NP» radica en primer lugar en el nivel cognitivo, por lo que si esperamos obtener una idea de «P versus NP», primero debemos preguntarnos: ¿Qué es NP?