¿Cómo sería un P = NP prueba de ser así, hipotéticamente?
https://stackoverflow.com/questions/900273
-
23-08-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPregunta
¿Sería un algoritmo de tiempo polinomial a un problema NP-completo específico, o sólo razonamientos abstractos que demuestran soluciones a los problemas NP-completos existen?
Parece que la una algoithm específico es mucho más útil. Con él, todo lo que tendremos que hacer para resolver un problema NP polinómicamente es para convertirlo en el problema NP-completo específico para el que la prueba tiene una solución, y que se realizan.
Solución
P = NP: "El problema 3SAT es un problema clásico completa NP En esta prueba. , demostramos un algoritmo para resolverlo que tiene un asintótica ligado de (n ^ 99 log log n). en primer lugar ... "
P = NP:. "Supongamos que había un algoritmo polinómico para la 3SAT problema Este implicaría que .... por lo que ..... implica que podemos hacer .... y luego ... y luego ... lo cual es imposible. todo esto fue predicada en un algoritmo de tiempo polinómico para 3SAT. por lo tanto P ! = NP. "Actualizar : Tal vez algo así como este documento (por P! = NP).
ACTUALIZA 2 He aquí un video de Michael Sipser esbozar una prueba para P! = NP
Otros consejos
Me llaman pesimista, pero será así:
...
∴, P ≠ NP
QED
Hay algunos meta-resultados sobre lo que un P = NP o P ≠ NP prueba puede no parecerse. Los detalles son bastante técnica, pero se sabe que la prueba no puede llegar
-
relativización , qué tipo de significa que la prueba debe hacer uso de la definición exacta de la máquina de Turing utilizado, ya que con algunas modificaciones ( "oráculos", al igual que las instrucciones CISC muy potentes añadidos al conjunto de instrucciones) P = NP, y con algunas otras modificaciones, P ≠ NP. Ver también esta entrada de blog para una buena explicación de relativización.
-
naturales , una propiedad de varias clásica pruebas,
-
o algebrizing , una generalización de relativización.
Se podría tomar la forma de demostrar que asumiendo P ≠ NP lleva a una contradicción.
No se pudo conectar a P y NP de una manera directa ... Muchos teoremas ahora se basan en P! = NP, por lo que se suponía que demuestra hecho de que no es verdad que haría una gran diferencia. Incluso probar algo así como relación constante aproximación para TS debe ser lo suficientemente IIRC. Creo que, existencia de NPI (GI) y otros conjuntos también se basa en P! = NP, así que hacer ninguna de ellas igual a P o NP podría cambiar la situación por completo.
En mi humilde opinión todo lo que sucede ahora en un nivel muy abstracto. Si alguien prueba algo acerca de P = /! = NP, que no tiene que mencionar ninguno de esos conjuntos o incluso un problema específico.
Set N igual a la identidad multiplicativa. Entonces NP = P. QED. ; -)
La forma más directa es demostrar que hay una solución en tiempo polinomial a los problemas de la clase NP-completo. Estos son los problemas que se encuentran en NP y son reducible a uno de los problemas NP conocido. Eso significa que usted podría dar un algoritmo más rápido para probar las href="http://portal.acm.org/citation.cfm?coll=GUIDE&dl=GUIDE&id=805047" planteada por Stephen cocinero o muchos otros que también han demostrado ser NP-completo. Ver papel seminal y este libro para problemas más interesantes. Se ha demostrado que si a resolver uno de estos problemas de toda la clase de complejidad se derrumba. Edit: Tengo que añadir que yo estaba hablando con mi amigo que está estudiando computación cuántica. A pesar de que no tenía ni idea de lo que significa, dijo que una prueba cierta / experimento? en el mundo cuántico podría hacer que toda la clase de complejidad, me refiero a todo el asunto, 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. Se podría tratar de contar el conjunto. Theres la prueba Robert / Seymore. Las personas también han intentado resolverlo utilizando la prueba diagonlization de probada eficacia (también se utiliza para mostrar que hay problemas que nunca se puede resolver). Razborov también demostró que si hay ciertas funciones unidireccionales entonces cualquier prueba no puede dar una resolución. Eso significa que se necesitarán nuevas técnicas con el fin de resolver esta cuestión.
Su sido 38 años desde que el documento original ha sido publicado y todavía no hay signo de una prueba. No sólo eso, sino que muchos de los problemas matemáticos que habían sido que presenta antes de la noción de clases de complejidad entró se ha demostrado que es NP. Para ello los matemáticos y científicos informáticos que muchos creen que algunos de los problemas son tan fundamentales que una nueva clase de matemáticas puede ser necesaria para resolver el problema. Tienes que tener en cuenta que la raza humana mejores mentes tiene que ofrecer han abordado este problema sin ningún éxito. Creo que debería ser, al menos, décadas antes de que alguien grietas del rompecabezas. Pero incluso si no hay una solución en tiempo polinomial las constantes o el exponente podría ser tan grande que sería inútil en nuestros problemas.
Hay una excelente encuesta disponible que debe responder a la mayoría de sus preguntas: http: // www .scottaaronson.com / documentos / pnp.pdf .
Sin duda, una prueba descriptiva es el más útil, pero hay otras categorías de la prueba: es posible, por ejemplo, para proporcionar 'pruebas de existencia' que demuestran que se trata de posible para encontrar una respuesta sin encontrar (o, a veces, incluso sugiriendo cómo encontrar) la respuesta.
Es probable que se vería casi exactamente igual que uno de estos
Buena pregunta; podría tomar cualquiera de las formas. Obviamente, el algoritmo específico sería más útil, sí, pero no hay ninguna determinar que esa sería la forma en que un teórico P = NP ocurriría prueba. Teniendo en cuenta que la naturaleza de los problemas NP-completos y qué tan comunes son, parecería que más esfuerzo se ha puesto en la solución de esos problemas que se ha puesto en la solución del lado del razonamiento teórico de la ecuación, pero eso es sólo una suposición.
Cualquier prueba no constructiva que P = NP realidad no lo es. Esto implicaría que el siguiente algoritmo explícito 3-SAT se ejecuta en tiempo polinómico:
Enumerar todos los programas. En redonda i , ejecutar todos los programas numerados menos de i para un paso. Si un programa termina con una satisfacer entrada a la fórmula volver true . Si un programa termina con un prueba formal de que hay tal entrada existe , el regreso false .
Si P = NP, entonces existe un programa que se ejecuta en O (poli (N)) y da salida a una entrada satisfactoria a la fórmula, si existe una fórmula tal.
Si P = CONP, existe un programa que se ejecuta en O (poli (N)) y da salida a una prueba formal de que no existe una fórmula, si no existe una fórmula.
Si P = NP, a continuación, ya que P es cerrado bajo complemento NP = CONP. Por lo tanto, existe un programa que se ejecuta en O (poli (N)) y hace ambas cosas. Ese programa es el k 'th programa en la enumeración. k es O (1) ! Dado que se ejecuta en O (poli (N)) nuestra simulación de fuerza bruta sólo requiere
k * O (poli (N)) + O (poli (N)) ^ 2
rondas una vez que alcanza el programa en cuestión. Como tal, la simulación de la fuerza bruta se ejecuta en tiempo polinómico!
(Tenga en cuenta que k es exponencial en el tamaño del programa; este enfoque no es realmente viable, pero sugiere que sería difícil de hacer una prueba no constructiva que P = NP, incluso si se diera el caso.)
En cierta medida, la forma tal prueba debe tener depende del punto de vista (= los axiomas que considere para ser verdad filosófica) - por ejemplo, como un constructivista usted exigir la construcción de un algoritmo real que requiere tiempo polinómico para resolver un problema NP-completo. Esto podría hacerse mediante el uso de la reducción, pero no con una prueba indirecta. De todos modos, lo que realmente parece ser muy poco probable:)
La prueba sería deducir una contradicción de a la suposición de que al menos un elemento (problema) de NP no es también un elemento de P.
