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

25

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?

BlueRaja - Danny Pflughoeft
fuente
1. Tenga en cuenta que la definición que está citando es para problemas de decisión. 2. Con respecto a su ejemplo de diofantina, no está afirmando que todos los sistemas existen un límite polinómico en el tamaño de las soluciones, ¿verdad?
Dmitri Chubarov
@Dmitri: Er, sí, estoy reclamando eso. El tamaño de la solución es exactamente el mismo que el tamaño del problema: si hay N incógnitas, la solución contiene N enteros. Y este es un problema de decisión: la solución entera (necesaria para verificar el caso "sí") sería su certificado .
BlueRaja - Danny Pflughoeft
19
La pregunta es, ¿qué tan grandes son los entrantes?
Artem Kaznatcheev
10
@ BlueRaja-DannyPflughoeft si tiene un alfabeto infinito para codificar sus enteros, entonces ya no está en la configuración estándar de la teoría de la complejidad. Con un alfabeto finito, el tamaño de la codificación crece con el valor de un número entero.
Dmitri Chubarov
Una solución al problema de detención simplemente devolvería "Sí", sin dar una pista de cuántos pasos simular para la verificación.
RemcoGerlich

Respuestas:

10

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.

Ben
fuente
26

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.Sf(n;x1,...,xk)nSx1xkf(n;x1,...,xk)=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.x1,...xk

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.x1,...,xknlogn

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 )NPp(N)NNPp(N)

Artem Kaznatcheev
fuente
Por supuesto, entiendo lo que significa "resolver una ecuación de diofantina": encontrará números que satisfacen la ecuación. No veo por qué el teorema de indecidibilidad de Matiyasevich o los conjuntos recursivamente enumerables necesitan ser traídos a la discusión. Pero creo que el último párrafo podría explicarlo ...
BlueRaja - Danny Pflughoeft
1
Bien, esta nueva edición lo explica, eso también explica por qué el problema de Detención no está en NP, ya que los pasos que se toman para detener podrían ser arbitrariamente grandes. ¡Gracias!
BlueRaja - Danny Pflughoeft
Mi edición sugerida fue eliminar los dos primeros párrafos. Los primeros dos párrafos explican por qué el décimo problema de Hilbert es indecidible, lo cual es completamente tangencial a la pregunta; simplemente restan valor al resto de la respuesta (¡de lo contrario, es una gran respuesta!) .
BlueRaja - Danny Pflughoeft
@ BlueRaja-DannyPflughoeft si el primer párrafo lo insultó, entonces puedo eliminarlo (aunque usted preguntó "¿qué hay de malo en mi comprensión?"). El segundo párrafo es necesario para establecer el problema de manera más formal, ya que no lo hace en su pregunta.
Artem Kaznatcheev
3
@ BlueRaja-DannyPflughoeft Es mejor si las preguntas y respuestas son independientes. Mi segundo párrafo establece el problema y explica lo que significa que este problema sea indecidible. Mi tercer párrafo da la respuesta rápida. Mis párrafos cuarto y quinto amplían eso con más detalle. Por lo que puedo decir, todos los párrafos son necesarios.
Artem Kaznatcheev
8

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

LpqM

  • xMp(|x|)(x,y)
  • xLyq(|x|)M(x,y)=1
  • xLyq(|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.

Rafael
fuente
"un verificador tiene que funcionar también en soluciones que no son soluciones" . Si está afirmando que el verificador necesita poder verificar respuestas "no", eso es incorrecto, eso sería co-NP . Y ya estoy al tanto de la segunda definición, pero estaba confundido sobre cómo podría ser equivalente a la primera, ya que una definición parece admitir el problema en la pregunta, mientras que la otra no.
BlueRaja - Danny Pflughoeft
@ BlueRaja-DannyPlughoeft: Mi observación es: los verificadores deben poder refutar las no soluciones. Si es consciente de esto, edite su pregunta en consecuencia; te hace ver bastante incognoscible.
Raphael
Es trivialmente obvio que el verificador ya refuta las no soluciones: simplemente inserte los números en la ecuación y vea si se cumple. Me temo que no entiendo a qué estás tratando de llegar.
BlueRaja - Danny Pflughoeft
@ BlueRaja-DannyPlughoeft: La "definición" que cita no especifica este comportamiento.
Raphael
-1

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.

Yu Li
fuente
1
No, la indecidibilidad del DEP (décimo problema de Hilbert) no se demostró hasta 1970, por Matiyesevich. El problema Entscheidungs ​​no es el décimo problema de Hilbert; se refiere a la validez de las fórmulas de la lógica de primer orden. Y, una vez más, el problema P vs. NP no es absolutamente un problema acerca de si los problemas indecidibles son verificables.
David Richerby
1
Si desea proporcionar más detalles, debe editar su publicación original.
Tom van der Zanden
@DavidRicherby Tenga en cuenta que la respuesta dada por Ben: «el conjunto de problemas que pueden decidir las NTM es idéntico al conjunto de problemas que pueden decidir los TM». Justo en este sentido, creo que la definición de NP confunde P con NP, y conduce a P = NP (NDTM). Si esta definición necesita ser cuestionada, entonces otras conclusiones deducidas de esta definición, como la equivalencia de un verificador determinista y un decisor no determinista, también deben ser cuestionadas.
Yu Li
@YuLi "conduce a P = NP (NDTM)". No tengo idea de lo que quieres decir con eso. Además, no veo la relevancia de señalar que las TM y las NTM deciden los mismos idiomas. Si no decidieran los mismos idiomas, las NTM serían un modelo de cálculo completamente irracional y es difícil imaginar que nos importe lo que puedan calcular en tiempo polinómico. En la teoría de la complejidad, estamos adoptando una visión más precisa y preguntando acerca de los recursos computacionales requeridos y la definición de NP no confunde eso en absoluto.
David Richerby
@DavidRicherby Gracias, he modificado mi respuesta de acuerdo con su comentario para aclarar la relación del problema Entscheidungs ​​y el décimo problema de Hilbert. Con respecto a la pregunta sobre la definición actual de NP, es difícil discutir en varias palabras. El objetivo de mi respuesta es solo evocar algunas reflexiones sobre este tema básico, ...
Yu Li
-2

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?

Yu Li
fuente
44
Esto parece ser un artículo de opinión sobre la definición de NP , no una respuesta a la pregunta. La definición de NP está bien. No confunde P con NP ; más bien, reconoce que P es un subconjunto de NP . Para mí, sería muy poco natural si P no fuera un subconjunto de NP . NP es una clase de problemas que se pueden resolver dentro de ciertos límites de recursos. Eso necesariamente incluye un montón de problemas fáciles ( P ) que pueden resolverse sin acercarse al límite de los recursos disponibles.
David Richerby
@DavidRicherby P y NP tienen la propiedad común de «certificado verificable en tiempo polinómico», pero esta propiedad no es la esencia de NP. Si esta propiedad se usa para definir NP, entonces P es un subconjunto de NP, y NP tiene P como su subconjunto (decidible) y en sí mismo (indecidible). Por lo tanto, uno se preguntaría si NP es decidible o indecidible. Al igual que el dilema anterior: ¿es la ecuación de Diofantina indecidible o decidible? Entonces, mi respuesta es sugerir investigar este dilema desde el punto de vista de la definición de NP: verificable, indecidible es no verificable!
Yu Li
Los problemas en NP son decidibles por definición: NP es la clase de problemas decididos por las máquinas de Turing no deterministas. Es fácil demostrar que este es exactamente el mismo conjunto de problemas que tienen certificados de longitud polinómica que pueden verificarse en tiempo polinómico. Si le preocupa que los problemas en NP no sean decidibles, entonces ha entendido mal algo.
David Richerby
Sí, me preocupa que los problemas en NP podrían no ser decidibles. Usted habla de la equivalencia de las dos definiciones de NP: NP es la clase de problemas decididos por las máquinas de Turing no deterministas; NP es la clase de problemas que tienen certificados de longitud polinómica verificados en tiempo polinómico. Dudo de esta equivalencia, porque uno trata sobre la existencia de un algoritmo para resolver un problema y el otro sobre la existencia de una solución para un problema. El dilema sobre la ecuación de diofantina puede estar directamente relacionado con esta equivalencia (ver más detalles de mi argumento: arxiv.org/abs/1501.01906 ).
Yu Li
2
@YuLi La equivalencia de las dos definiciones de NP es tan sencilla que se enseña en las clases de teoría de complejidad de pregrado. Sugiero no subir a ArXiv si no entiende los conceptos básicos del campo.
David Richerby