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.
fuente
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.
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.
fuente