¿comprobar es más fácil que encontrar?
encontrar una solución a un problema debería ser más difícil que comprobar que una solución es correcta. Eso parece obvio Si alguna vez has resuelto un sudoku, o resuelto un cubo de Rubik, o jugado una partida de ajedrez. Pero esa afirmación, por intuitiva que parezca, nos lleva directamente a una de las preguntas matemáticas más profundas planteadas por nuestra civilización.
los problemas de tiempo polinómico no determinista (o NP) son aquellos en los que puede verificar fácilmente que una respuesta sea correcta., En contraste, los problemas de tiempo polinómico (O P) Son aquellos en los que encontrar la respuesta es fácil. Si puede encontrar la respuesta, entonces ha comprobado que es correcta, por lo que cada problema en P también está en NP. Decimos Que P es una subclase de NP. Sin embargo, no sabemos si hay algún problema particular en NP que no esté en P, y eso es lo que llamamos el problema P vs NP.
el problema P vs NP es uno de los problemas sin resolver más centrales en matemáticas y Ciencias de la computación teórica. Incluso hay un premio Clay Millennium que ofrece un millón de dólares por su solución., Sin embargo, es probable que haya formas mucho más fáciles de convertirse en millonario que resolver P vs NP!
hubo un zumbido recientemente cuando alguien pretendió resolverlo en arXiv, aunque una brecha en la prueba se encontró rápidamente. Dado el reciente interés en el problema y su lugar central en las matemáticas, lo discuto en el blog de esta semana.
Sudoku
Si se te da un rompecabezas de Sudoku rellenado en un periódico, puedes tirarlo a la papelera. Pero si lo desea, puede escanear a través de las filas, columnas y celdas 3 x 3 para decir que es una solución válida: cada uno de 1, 2, 9, 9 debe ocurrir exactamente una vez., Esto es análogo a NP, ya que es relativamente fácil comprobar si una solución es correcta.
sin embargo, si te doy un Sudoku parcialmente lleno, puede ser difícil encontrar la solución. Esa es la alegría y el desafío de este tipo de rompecabezas. Por lo tanto, estar en NP no parece implicar inmediatamente que el problema sea fácil de encontrar una solución. Esa intuición está en el corazón del problema P vs NP.
formulación precisa
para entender P y NP con mayor precisión, necesitamos comprender mejor los algoritmos y medir su velocidad. Se plantean problemas con algunas entradas y salidas fijas, ya sea sí o NO. La entrada es una longitud dada, digamos n, donde n es un entero positivo. Esto representa el número de bits que se necesitan para expresar la entrada. Un algoritmo es un método o procedimiento para resolver un problema. Los algoritmos proporcionan instrucciones en cada paso de un cálculo y deben terminar., Los pasos pueden ser segundos, milisegundos o algún otro intervalo de tiempo fijo que dependa del problema.
la complejidad de un problema es el tiempo de ejecución mínimo en el peor de los casos sobre todos los algoritmos posibles que resuelven el problema en función de la longitud de la entrada. En otras palabras, mide cuánto tiempo se tarda en resolver el problema con el algoritmo más rápido pero con la entrada del peor caso.
un problema es solucionable en tiempo polinómico si se le da una entrada de longitud n, su complejidad está limitada por encima por la función polinómica nm para algún entero no negativo m., El conjunto de todos los problemas solucionables en tiempo polinómico se denota por P.
estar en P no significa necesariamente que el problema sea factible. Por ejemplo, si toma N1000 pasos para ejecutar el algoritmo, entonces será irremediablemente lento incluso para n pequeños. los problemas polinómicos no deterministas (o NP) son aquellos en los que puede verificar si la respuesta sí es correcta en tiempo polinómico.
NP-hardness
Un problema es NP–hard si un algoritmo de tiempo polinómico para ello implicaría un algoritmo de tiempo polinómico para cada problema en NP. Por lo tanto, si un problema NP-hard estaba en P, entonces P = NP., Los problemas NP-hard son al menos tan difíciles como cualquier problema en NP. Un problema NP-completo es uno que es NP-duro y en NP.
un problema clásico de NP-complete es encontrar un ciclo de Hamilton. Para esto, supongamos que tenemos una red de ciudades conectadas por carreteras. El problema es visitar cada ciudad usando carreteras (¡no se permiten aviones!) y volver al principio. Esto parece fácil para un pequeño número de ciudades, pero si se le dieron cientos de ellos, entonces se vuelve difícil., Se conocen miles de otros problemas NP-completos que surgen en la teoría de grafos, la teoría de números, la geometría y otras áreas de las matemáticas y la informática.
¿Cuál es la respuesta, realmente?
Si tuviera que apostar, entonces asumiría que P no es igual a NP, y creo que la mayoría de los expertos estarían de acuerdo. Tendríamos que ser terriblemente tontos para no ver cómo todos los miles de problemas NP-completos no tienen un algoritmo de tiempo polinómico. Pero como especie, tonto es nuestra posición por defecto por lo que nadie puede decir cuál es la respuesta con 100% de certeza.,
Lo interesante del problema P vs NP es que apunta a lo limitado que es nuestra comprensión para demostrar que ciertos problemas no tienen soluciones rápidas. Esto es parte de un tema más amplio en el campo de la teoría de la complejidad computacional, que estudia docenas de otras clases de complejidad. Echa un vistazo al zoológico de complejidad para ver una lista de estas clases. En su mayor parte, está abierto a mostrar que varias clases de complejidad (a menudo de sonido exótico) son subclases propias entre sí. Por ejemplo, se desconoce si NL es una subclase de P, y no sabemos si FPT es una subclase de W.,
independientemente de su veracidad, es probable que el problema P vs NP permanezca abierto durante algún tiempo. A menos que se demuestre que P = NP, el Sudoku permanece seguro.
Anthony Bonato