algorithm - problema - ¿Cómo sería hipotéticamente una prueba de P=NP?
p vs np youtube (15)
¿Sería un algoritmo de tiempo polinomial para un problema específico de NP-completo, o solo razonamientos abstractos que demuestran que existen soluciones para los problemas de NP-completo?
Parece que un algoritmo específico es mucho más útil. Con esto, todo lo que tendremos que hacer para resolver polinomialmente un problema de NP es convertirlo en el problema específico de NP-completo para el cual la prueba tiene una solución, y hemos terminado.
Buena pregunta; Podría tomar cualquiera de las dos formas. Obviamente, el algoritmo específico sería más útil, sí, pero no hay ninguna determinación de que esa sería la forma en que se produciría una prueba teórica de P = NP. Dada la naturaleza de los problemas de NP-completos y cuán comunes son, parece que se ha puesto más esfuerzo en resolver esos problemas que en resolver el lado del razonamiento teórico de la ecuación, pero eso es solo una suposición.
Ciertamente, una prueba descriptiva es la más útil, pero hay otras categorías de prueba: es posible, por ejemplo, proporcionar "pruebas de existencia" que demuestren que es posible encontrar una respuesta sin encontrar (o, a veces, incluso sugiriendo cómo para encontrar) esa respuesta.
Cualquier prueba no constructiva de que P = NP realmente no lo es. Implicaría que el siguiente algoritmo explícito 3-SAT se ejecuta en tiempo polinomial:
Enumerar todos los programas. En la ronda i , ejecute todos los programas numerados menos que i para un paso. Si un programa termina con una entrada satisfactoria a la fórmula , devuelva verdadero . Si un programa termina con una prueba formal de que no existe tal entrada , devuelva false .
Si P = NP, entonces existe un programa que se ejecuta en O (poli (N)) y genera una entrada satisfactoria a la fórmula, si existe tal fórmula.
Si P = coNP, existe un programa que se ejecuta en O (poli (N)) y genera una prueba formal de que no existe una fórmula, si no existe una fórmula.
Si P = NP, entonces como P está cerrado bajo el complemento NP = coNP. Por lo tanto, existe un programa que se ejecuta en O (poli (N)) y hace ambos. Ese programa es el programa k ''th en la enumeración. k es O (1) ! Dado que se ejecuta en O (poli (N)), nuestra simulación de fuerza bruta solo requiere
k * O (poli (N)) + O (poli (N)) ^ 2
Redondea una vez que llega al programa en cuestión. Como tal, ¡la simulación de fuerza bruta se ejecuta en tiempo polinomial!
(Tenga en cuenta que k es exponencial en el tamaño del programa; este enfoque no es realmente factible, pero sugiere que sería difícil hacer una prueba no constructiva de que P = NP, incluso si fuera el caso).
Establecer N igual a la identidad multiplicativa. Entonces NP = P. QED. ;-)
Hasta cierto punto, la forma que debe tener dicha prueba depende de su punto de vista filosófico (= los axiomas que considera verdaderos), por ejemplo, como un contructivist exigiría la construcción de un algoritmo real que requiera tiempo polinomial para resolver Un problema NP-completo. Esto se podría hacer usando reducción, pero no con una prueba indirecta. De todos modos, realmente parece ser muy poco probable :)
Hay algunos meta-results sobre cómo no puede verse una prueba de P = NP o P ≠ NP. Los detalles son bastante técnicos, pero se sabe que la prueba no puede ser
relativizing , que significa que la prueba debe hacer uso de la definición exacta de la máquina de Turing utilizada, porque con algunas modificaciones ("oráculos", como instrucciones CISC muy poderosas agregadas al conjunto de instrucciones) P = NP, y con algunas otras modificaciones , P ≠ NP. Vea también esta publicación del blog para una buena explicación de la relativización.
natural , una propiedad de varias pruebas de complejidad de circuitos clásicos,
O algebrizing , una generalización de la relativización.
La prueba deduciría una contradicción al suponer que al menos un elemento (problema) de NP no es también un elemento de P.
Llámame pesimista, pero será así:
...
∴, P ≠ NP
QED
P = NP: "El problema 3SAT es un problema clásico NP completo. En esta prueba, demostramos un algoritmo para resolverlo que tiene un límite asintótico de (n ^ 99 log log n). Primero, nosotros ..."
P! = NP: "Supongamos que hubo un algoritmo polinomial para el problema 3SAT . Esto implicaría que ... lo que ... implica que podemos hacer ... y luego ... y luego ... lo cual es imposible. Todo esto se basó en un algoritmo de tiempo polinomial para 3SAT. Por lo tanto, P! = NP ".
ACTUALIZACIÓN : Quizás algo como este documento (para P! = NP).
ACTUALIZACIÓN 2 : Aquí hay un video de Michael Sipser bosquejando una prueba para P! = NP
Podría tomar la forma de demostrar que suponiendo que P ≠ NP conduce a una contradicción.
Probablemente se vería casi exactamente como uno de these
Probablemente sería en la forma de una reducción de un problema de NP a un problema de P. Vea la página de Wikipedia sobre las reductions .
O
Como esta proof propuesta por Vinay Deolalikar.
Puede que no esté conectado a P y NP de una manera directa ... Muchos teoremas ahora se basan en P! = NP, por lo que demostrar que un hecho asumido es falso sería una gran diferencia. Incluso probar algo como una aproximación de relación constante para TS debería ser suficiente IIRC. Creo que la existencia de NPI (GI) y otros conjuntos también se basa en P! = NP, por lo que hacer que cualquiera de ellos sea igual a P o NP podría cambiar la situación por completo.
En mi humilde opinión todo sucede ahora en un nivel muy abstracto. Si alguien prueba algo sobre P = /! = NP, no tiene que mencionar ninguno de esos conjuntos o incluso un problema específico.
La forma más directa es demostrar que existe una solución de tiempo polinomial para los problemas de la clase NP-completa. Estos son problemas que están en NP y se pueden reducir a uno de los problemas conocidos de np. Eso significa que podría dar un algoritmo más rápido para probar el problema original planteado por Stephen Cook o muchos otros que también han demostrado ser NP-Complete. Vea el artículo seminal de Richard Karp y este libro para problemas más interesantes. Se ha demostrado que si soluciona uno de estos problemas, la clase de complejidad completa colapsará. edición: debo agregar que estaba hablando con mi amigo que está estudiando computación cuántica. Aunque no tenía ni idea de lo que significa, ¿dijo que una cierta prueba / experimento? en el mundo cuántico podría hacer que toda la clase de complejidad, me refiero a todo, discutible. Si alguien aquí sabe más sobre esto, por favor responda.
También ha habido numerosos intentos para el problema sin dar un algoritmo formal. Podrías intentar contar el conjunto. Hay la prueba de Robert / Seymore. Las personas también han intentado resolverlo utilizando la prueba de diagonización probada (también se usa para mostrar que hay problemas que nunca se pueden resolver). Razborov también demostró que si hay ciertas funciones unidireccionales, cualquier prueba no puede dar una resolución. Eso significa que se requerirán nuevas técnicas para resolver esta pregunta.
Han pasado 38 años desde que se publicó el artículo original y todavía no hay señales de una prueba. No solo eso, sino muchos de los problemas que los matemáticos habían estado planteando antes de que llegara la noción de clases de complejidad se ha demostrado que es NP. Por lo tanto, muchos matemáticos e informáticos creen que algunos de los problemas son tan fundamentales que puede ser necesario un nuevo tipo de matemáticas para resolver el problema. Hay que tener en cuenta que las mejores mentes que la raza humana tiene para ofrecer han abordado este problema sin ningún éxito. Creo que deberían pasar al menos décadas antes de que alguien rompa el rompecabezas. Pero incluso si hay una solución de tiempo polinomial, las constantes o el exponente podrían ser tan grandes que sería inútil en nuestros problemas.
Hay una excelente encuesta disponible que debe responder la mayoría de sus preguntas: http://www.scottaaronson.com/papers/pnp.pdf .