Explicar la prueba por Vinay Deolalikar que P! = NP [cerrada]

Question

Recientemente ha habido un papel flotando por Vinay Deolalikar de HP Labs que afirma haber demostrado que P! = NP .

Podría alguien explicar cómo funciona esta prueba para nosotros menos inclinado matemáticamente personas?

Answer 1

Sólo he Escaneé a través del papel, pero aquí está un resumen general de cómo se cuelga todos juntos.

A partir de la página 86 del documento.

  

... tiempo polinómico   algoritmos de alcanzar el éxito al sucesivamente   “Romper” el problema en   subproblemas más pequeños que se unen a   entre sí a través condicional   independencia. En consecuencia, polinomio   algoritmos de tiempo no pueden resolver   problemas en los regímenes donde los bloques cuyos   orden es el mismo que el subyacente   instancia problema requiere simultánea   resolución.

Otras partes del documento muestran que ciertos problemas NP no puede ser disuelta de esta manera. Así NP / = P

La mayor parte del trabajo se dedica a la definición de independencia condicional y probando estos dos puntos.

Answer 2

Dick Lipton tiene un bonito entrada de blog sobre el papel y sus primeras impresiones de él. Por desgracia, también es técnico. Por lo que puedo entender, la principal innovación de Deolalikar parece ser el uso de algunos conceptos de la física estadística y la teoría de modelos finitos y atarlos al problema.

Estoy con Rex M con éste, algunos resultados, sobre todo las matemáticas no se pueden expresar a las personas que carecen del dominio de la técnica.

Answer 3

Me gusta esto ( http://www.newscientist.com/article/dn19287-p--np-its-bad-news-for-the-power-of-computing.html ):

  

Su argumento gira en torno a una tarea en particular, el problema satisfacibilidad de Boole, que pregunta si una colección de declaraciones lógicas todo puede ser simultáneamente verdaderas o si se contradicen entre sí. Esto es conocido por ser un problema NP.

     

Deolalikar afirma haber demostrado que   no hay un programa que puede completar   rápidamente desde cero, y que   por lo tanto, no es un problema P. Su   argumento implica el uso ingenioso de   la física estadística, ya que utiliza una   estructura matemática que sigue   muchas de las mismas reglas que un azar   sistema físico.

Los efectos de la anterior puede ser bastante significativo:

  

Si el resultado está, probaría   que las dos clases P y NP no son   idéntica, e imponer límites severos a   lo que los ordenadores pueden lograr -   lo que implica que muchas de las tareas pueden ser   fundamentalmente, irreduciblemente complejo.

     

Para algunos problemas - incluyendo   factorización - el resultado no lo hace   dicen claramente si se pueden resolver   con rapidez. Pero una gran subclase de   problemas llamados "NP-completo" serían   condenado. Un ejemplo famoso es el   problema del vendedor ambulante - encontrar   la ruta más corta entre un conjunto de   las ciudades. Tales problemas se pueden comprobar   rápidamente, pero si P ? NP entonces hay   ningún programa de ordenador que puede completar   ellos rápidamente desde cero.

Answer 4

Este es mi entendimiento de la técnica de la prueba: se utiliza lógica de primer orden para caracterizar todos los algoritmos de tiempo polinómico, y luego muestra que para los grandes problemas del SAT con ciertas propiedades que ningún algoritmo de tiempo polinomial puede determinar su satisfacibilidad.

Answer 5

Otra forma de pensar en ello, que puede ser del todo mal, pero es mi primera impresión como lo estoy leyendo en la primera pasada, es que pensamos de asignar / borrar los términos de la satisfacción del circuito como formando y rompiendo las agrupaciones de 'estructura ordenada', y que está a continuación, utilizando la física estadística para demostrar que no hay suficiente velocidad en las operaciones polinómicas para realizar esas operaciones en un "espacio de fase" particular de operaciones, debido a que estos "clusters" terminan siendo demasiado aparte.

Answer 6

Esta prueba tendría que cubrir todas las clases de algoritmos, como continua optimización global .

Por ejemplo, en el problema 3-SAT Tenemos que evaluar las variables de cumplir con todas las alternativas de triples de estas variables o sus negaciones. Mirada que x OR y se puede cambiar en la optimización

((x-1)^2+y^2)((x-1)^2+(y-1)^2)(x^2+(y-1)^2)

y términos análoga para siete alternativa de tres variables.

Encontrar el mínimo global de una suma de dichos polinomios de todos los términos resolvería nuestro problema. ( fuente )

Se va de técnicas estándar combinatorias a los métodos continuos using_gradient mundo, mínimas locales eliminación de métodos, algoritmos evolutivos. Es completamente diferente Unido - análisis numérico - No creo que tal prueba podría realmente cubierta (?)

Answer 7

Vale la pena señalar que con las pruebas, "el diablo está en los detalles". La visión general de alto nivel es, obviamente, algo como:

  

Algunas algún tipo de relación   entre artículos, muestran que este   relación implica X y que   Y implica y por lo tanto mi argumento es   se muestra.

Es decir, puede ser a través de inducción o cualquier otra forma de probar cosas, pero lo que digo es el alto nivel de visión general es inútil. No hay punto explicarla. Aunque la pregunta en sí misma se relaciona con la informática, que es mejor dejar a los matemáticos (que se cree que es ciertamente muy interesante).