math - polynomial - unsolved problems in computer science

Explique la prueba de Vinay Deolalikar que P!=NP

Question

Recientemente, Vinay Deolalikar ha publicado un documento en HP Labs, que afirma haber demostrado que P! = NP .

¿Podría alguien explicar cómo funciona esta prueba para nosotros, las personas menos inclinadas matemáticamente?

Answer 1

Dicha prueba debería cubrir todas las clases de algoritmos, como la optimización global continua .

Por ejemplo, en el problema de 3-SAT tenemos que evaluar variables para cumplir con todas las alternativas de triples de estas variables o sus negaciones. Mira que x OR y se puede cambiar para optimizar

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

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

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

Se está pasando de las técnicas combinatorias estándar al mundo continuo utilizando métodos de gradiente, métodos de eliminación de mínimos locales, algoritmos evolutivos. Es un reino completamente diferente: análisis numérico: no creo que esa prueba realmente pueda cubrir (?)

Answer 2

Dick Lipton tiene una buena entrada en el blog sobre el periódico y sus primeras impresiones al respecto. Desafortunadamente, también es técnico. Por lo que puedo entender, la principal innovación de Deolalikar parece ser utilizar algunos conceptos de física estadística y teoría de modelos finitos y vincularlos al problema.

Estoy con Rex M con este, algunos resultados, en su mayoría matemáticos, no se pueden expresar a las personas que carecen de la maestría técnica.

Answer 3

Esta es mi comprensión de la técnica de prueba: utiliza la lógica de primer orden para caracterizar todos los algoritmos de tiempo polinomiales, y luego muestra que para los grandes problemas SAT con ciertas propiedades que ningún algoritmo de tiempo polinomial puede determinar su satisfiability.

Answer 4

Me gustó 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 particular, el problema de satisfacibilidad booleana, que pregunta si una colección de enunciados lógicos puede ser simultáneamente verdadera o si se contradicen entre sí. Se sabe que esto es un problema NP.

Deolalikar afirma haber demostrado que no existe un programa que pueda completarlo rápidamente desde cero, y que, por lo tanto, no es un problema de 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 sistema físico aleatorio.

Los efectos de lo anterior pueden ser bastante significativos:

Si el resultado se mantiene, probaría que las dos clases P y NP no son idénticas e imponen límites severos a lo que las computadoras pueden lograr, lo que implica que muchas tareas pueden ser fundamentalmente irreductiblemente complejas.

Para algunos problemas, incluida la factorización, el resultado no indica claramente si se pueden resolver rápidamente. Pero una gran subclase de problemas llamada "NP-completo" estaría condenada al fracaso. Un ejemplo famoso es el problema del vendedor ambulante: encontrar la ruta más corta entre un conjunto de ciudades. Dichos problemas se pueden verificar rápidamente, pero si P ≠ NP no existe un programa informático que pueda completarlos rápidamente desde cero.

Answer 5

Otra forma de pensar sobre esto, que puede ser completamente errónea, pero es mi primera impresión cuando la leo en la primera pasada, es que pensamos en asignar / borrar términos en la satisfacción del circuito como formando y rompiendo grupos de ''ordenados''. estructura, y que está usando física estadística para mostrar que no hay suficiente velocidad en las operaciones polinomiales para realizar esas operaciones en un "espacio de fase" particular de las operaciones, porque estos "grupos" terminan demasiado separados.

Answer 6

Solo he escaneado el documento, pero aquí hay un resumen aproximado de cómo todo se junta.

De la página 86 del documento.

... los algoritmos de tiempo polinomiales tienen éxito al "dividir" sucesivamente el problema en subproblemas más pequeños que se unen entre sí a través de la independencia condicional. Por consiguiente, los algoritmos de tiempo polinomiales no pueden resolver problemas en regímenes en los que los bloques cuyo orden es el mismo que el caso subyacente del problema requieren resolución simultánea.

Otras partes del documento muestran que ciertos problemas NP no se pueden dividir de esta manera. Por lo tanto NP / = P

Gran parte del trabajo se dedica a definir la independencia condicional y a probar estos dos puntos.

Answer 7

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

Algunos algún tipo de relación entre los elementos, muestran que esta relación implica X y eso implica Y y, por lo tanto, se muestra mi argumento.

Quiero decir, puede ser a través de Induction o cualquier otra forma de probar cosas, pero lo que estoy diciendo es que la descripción general de alto nivel es inútil. No tiene sentido explicarlo. Aunque la pregunta en sí se relaciona con la informática, es mejor dejarla en manos de los matemáticos (aunque ciertamente es increíblemente interesante).