Buscando fuente de literatura para la siguiente idea

12

Estoy bastante seguro de que no soy el primero en considerar la idea que voy a presentar. Sin embargo, sería útil si puedo encontrar alguna literatura relacionada con la idea.

La idea es construir una máquina de Turing M con la propiedad de que si P = NP, entonces M resolverá 3-SAT en tiempo polinómico. (La elección de 3-SAT es arbitraria. Podría ser realmente cualquier problema en NP).

Para ser claros, esto no es una afirmación de que P = NP. De hecho, creo lo contrario. Simplemente afirmo que si P = NP, entonces M proporcionará una solución de tiempo polinomial. Si está buscando una solución eficiente, debo advertir que esto está lejos de ser eficiente.

M se construye de la siguiente manera: primero, suponga una codificación canónica para todas las máquinas de Turing y aplique una numeración a estas máquinas. Entonces, hay una máquina de Turing número 1, una número 2, etc. La idea de una máquina de Turing universal que pueda leer el formato de una máquina provista y luego simular que la máquina está funcionando en una entrada separada es bastante conocida. M empleará una máquina universal de Turing para construir y simular cada máquina de Turing a su vez.

Primero simula el funcionamiento de Turing Machine 1 para un solo paso.
Luego observa la salida de Turing Machine 1.
Simula el funcionamiento de Turing Machine 1 durante dos pasos y observa la salida, luego procede a simular Turing Machine 2 durante 2 pasos. Continúa y se repite de esta manera, a su vez ejecuta Turing Machine 1 para k pasos, luego 2 para k pasos ... luego, finalmente, mecaniza k para k pasos.

Después de cada ejecución de simulación, examina la salida de la ejecución. Si la salida es una asignación de variables que satisfacen la instancia del problema 3-SAT, M se detiene en un estado de aceptación. Si, por otro lado, la salida es una cadena de prueba en algún lenguaje de prueba verificable con el resultado comprobado de que la instancia del problema no es satisfactoria, M se detiene en un estado de rechazo. (Para un lenguaje de prueba, podríamos, por ejemplo, usar los Axiomas de Peano con lógica de segundo orden y los axiomas lógicos básicos de estilo Hilbert. Lo dejo como un ejercicio para que el lector descubra que si P = NP, un valor válido el lenguaje de prueba existe y es verificable en tiempo polinómico).

Reclamaré aquí que M resolverá 3-SAT en tiempo polinómico si y solo si P = NP. Eventualmente, el algoritmo encontrará una máquina mágica de Turing con el número K, que resulta ser un solucionador eficiente para el problema 3-SAT, y es capaz de proporcionar una prueba de sus resultados para el éxito o el fracaso. K eventualmente se simulará ejecutando pasos poli (strlen (input)) para algunos polinomios. El polinomio para M es aproximadamente el cuadrado del polinomio para k en el factor más grande, pero con algunas constantes terribles en el polinomio.

Para reiterar mi pregunta aquí: quiero saber si hay una fuente de literatura que emplee esta idea. Estoy algo menos interesado en discutir la idea misma.

Provincia de Bill
fuente

Respuestas:

16

Parece que esta idea se atribuye a Levin (se llama búsqueda óptima). Creo que este hecho es bien conocido. Por ejemplo, en Wikipedia se describe un algoritmo similar , aunque se utiliza el problema de suma de subconjuntos. En este artículo de scholarpedia puede encontrar varias referencias sobre el tema, incluido un puntero al algoritmo original y algunos otros algoritmos de búsqueda óptimos.

φP=NPφ

Comentario 2: Como Jaroslaw Blasiok señaló en otra respuesta, este algoritmo no decide Sat solo suponiendo P = NP.

Mateus de Oliveira Oliveira
fuente
Acabo de encontrar la referencia de Wikipedia, y de hecho, menciona a Levin, pero sin citar. Puede ser que esto simplemente se haya convertido en folklore, pero nunca se haya usado en la literatura publicada. De todos modos, esto es útil. Gracias.
Bill Province
Bienvenido. Encontré una página de inicio con varias referencias sobre el tema. Edité la respuesta para incluirla.
Mateus de Oliveira Oliveira
6

La idea de ejecutar en diagonal todas las máquinas de Turing posibles ha sido utilizada previamente por Leonid Levin en lo que ahora se conoce como Levins Universal Search. Desafortunadamente, y contrariamente a la idea errónea extremadamente común, por lo que sé, las variaciones en la búsqueda universal de Levins NO son capaces de proporcionar algoritmos explícitos para resolver SAT (problema de decisión) en tiempo polinómico, dado el supuesto de que P = NP, y tampoco su algoritmo .

La advertencia del razonamiento propuesto radica (como muy a menudo) en el "ejercicio fácil que le queda al lector": no pude probar el ejercicio yo mismo y no creo que su afirmación sea cierta, a saber:

Suponiendo que P = NP, hay un tamaño polinómico que ZFC prueba de insatisfacción de una fórmula booleana dada.

Por otra parte: no puedo ver cómo demostrar la existencia de ZFC polinomialmente corto demuestra la insatisfacción bajo el supuesto (más fuerte) de que "P = NP es demostrable en ZFC". Sin embargo, se vuelve fácil bajo un supuesto aún más fuerte, a saber:

(*) Existe una máquina M funcionando en tiempo polinómico que resuelve SAT de manera demostrable.

Y esta es, creo, la suposición correcta bajo la cual su algoritmo resuelve SAT en tiempo polinómico. Más arriba por "resuelve probablemente SAT" quiero decir: existe una máquina M y una prueba de ZFC de que M resuelve SAT.

Tenga en cuenta que esta suposición sigue siendo un poco más débil que la siguiente: (**) Existe la máquina M, que probablemente se ejecuta en tiempo polinómico y resuelve de manera comprobable SAT.

Bajo (**) uno puede tener una construcción explícita que logre el mismo objetivo, lo que es aún más simple: enumere todas las pruebas de ZFC hasta encontrar la máquina correcta M (pasar tiempo constante), y luego ejecute M en una instancia determinada.

Es cierto, sin embargo, que bajo la suposición de P = NP existe un sistema de prueba polinomialmente verificable con pruebas cortas de insatisfacción de la fórmula dada. Lamentablemente, no conocemos ni el sistema de prueba ni el verificador de forma manual, y no es útil en esta configuración.

f1(x)

Tenga en cuenta que este esquema se aplica, por ejemplo, al problema FACTORING; aquí f es solo multiplicación (definida solo para factores distintos de \ pm 1) y B es comprobación de primaridad. Por lo tanto, la búsqueda universal de Levins sería (hasta un factor constante) un algoritmo óptimo para FACTORING. Dado que el algoritmo óptimo es más lento que el algoritmo conocido para la verificación de primaridades, en el otro caso la verificación de primaridades se vuelve dominante.

NPcoNP

Jarosław Błasiok
fuente
1
Si P = NP entonces co-NP = co-P = P = NP. Entonces, LA INSATISFIABILIDAD está en NP, también los testigos de tamaño polinómico: no es necesario invocar una máquina de Turing. ¿No puedes convertir a ese testigo en una prueba de ZFC de que la fórmula no es satisfactoria? No estoy al tanto de la mecánica de la prueba de ZFC, pero la intuición que he recibido de varios lugares es que, a menos que se trate de "cosas raras", ZFC corresponde a todas las cosas que creías que podrías probar de todos modos, antes Has oído hablar de la teoría de conjuntos. No es probable que los objetos finitos, como una fórmula booleana y un testigo polinómico de su insatisfacción, sean extraños.
David Richerby
Sí, si P = NP, entonces UNSAT está en NP y tiene un testigo de tamaño polinómico. A saber: testigo de tamaño cero, todo el trabajo lo realiza el verificador, ¿verdad? Solo tengo una idea en mente de cómo convertir este testigo de tamaño cero en ZFC prueba de insatisfacción: dar una prueba de ZFC de que mi máquina realmente resuelve UNSAT, y luego mostrar una ejecución de esta máquina en la fórmula; eso sería una prueba válida, y esto corresponde al hecho de que el algoritmo propuesto por OP funciona bajo (*). Pero, ¿qué pasaría si hubiera alguna máquina complicada que simplemente resuelve el SAT, pero este hecho no es demostrable? No es que crea que sea el caso
Jarosław Błasiok
1
La idea errónea a la que me refiero es: "si P = NP, entonces la Búsqueda universal de Levins proporciona un algoritmo de tiempo polinómico que resuelve el problema NP-completo" o, como a veces se dice: "Es imposible tener solo una prueba no constructiva de P = NP, porque del algoritmo de Levins ". Ambos son falsos: la formulación de Wikipedia presenta un método que se detiene en polytime en las instancias YES de SUBSET SUM, pero no se detiene en absoluto en las instancias NO; no es un algoritmo que decide la suma de subconjuntos en polytime. La formulación OP es mejor para el propósito, pero necesita una suposición más fuerte que P = NP para decidir SAT en polytime.
Jarosław Błasiok
1
NPcoNP
1
Ahora, la forma de lidiar con esto, ya que no conoce el verificador explícito para el problema UNSAT, sería tratar de encontrar una prueba corta en alguna lógica formal que ya conozcamos y podamos verificar (que sean axiomas de ZFC o Peano, estamos sin embargo, es más probable que encuentre una breve prueba en el primero), que esta instancia no es satisfactoria. Pero si se quiere demostrar que hay una prueba tan corta en esta lógica formal, se necesita una suposición más fuerte que P = NP.
Jarosław Błasiok