el problema P versus NP envejecido
Entonces, ¿qué es el problema P versus NP?
para el registro, el status quo es que P≠NP.
P (tiempo polinómico) se refiere a la clase de problemas que pueden ser resueltos por un algoritmo en tiempo polinómico. Los problemas en la clase P pueden variar desde cualquier cosa tan simple como la Multiplicación hasta encontrar el número más grande en una lista. Son el conjunto de problemas relativamente «más fácil».
NP (tiempo polinómico no determinista) se refiere a la clase de problemas que pueden ser resueltos en tiempo polinómico por un ordenador no determinista., Esta es esencialmente otra forma de decir «si tengo un poder de cómputo Ilimitado (es decir, tantos ordenadores como necesito), soy capaz de resolver cualquier problema en tiempo polinómico como máximo». Más intuitivamente, sin embargo, se refiere a la clase de problemas que actualmente, no tiene forma de encontrar una respuesta rápida (tiempo polinómico) suficiente, pero se puede verificar rápidamente (en tiempo polinómico) si se proporciona la solución al problema. El término verificado aquí significa que uno es capaz de comprobar que la solución proporcionada es realmente correcta.
claramente, basado en la definición anterior, P N NP., Echemos un vistazo a un ejemplo para ilustrar este problema abstracto.
uno de los ejemplos más comunes pero efectivos es el Sudoku. Dada una cuadrícula de Sudoku sin resolver (9 x 9, por ejemplo), un algoritmo tardaría bastante tiempo en resolver una. Sin embargo, si la cuadrícula de 9 x 9 aumenta a una cuadrícula de 100 x 100 o 10,000 x 10,000, el tiempo que tomaría resolverla aumentaría exponencialmente porque el problema en sí se vuelve significativamente más difícil., Sin embargo, dada una cuadrícula de Sudoku resuelta (de 9 x 9), es bastante sencillo verificar que la solución en particular es correcta incluso si el tamaño escala a 10,000 por 10,000. Sería más lento, pero el tiempo para comprobar una solución aumenta a un ritmo más lento (exponencialmente).
hay muchos otros problemas de NP por ahí, incluyendo el problema de la mochila y el problema de los vendedores ambulantes, y son similares en que son difíciles de resolver pero rápidos de verificar., El problema fundamental que estamos tratando de resolver aquí es:
¿ser capaz de reconocer rápidamente las respuestas correctas de NP significa que también hay una forma rápida de encontrarlas?
Si es así (es decir, P = NP), esto podría cambiar mucho la forma en que vemos estos problemas NP porque eso significa que hay una forma rápida de resolver todos estos problemas, solo que no hemos sido capaces de averiguar cómo, todavía.
si esto no es lo suficientemente complicado, vamos a darle vida.,
entre estos problemas NP, existe un rey de todos los problemas que los investigadores llaman NP-problemas completos. Formalmente, son un conjunto de problemas para cada uno de los cuales cualquier otro problema NP puede ser reducido (abordado a continuación) en tiempo polinómico y cuya solución aún puede ser verificada en tiempo polinómico. Esto significa que cualquier problema NP puede transformarse en un problema NP-completo.
informalmente, son los» más difíciles » de los problemas de NP., Por lo tanto, si cualquier problema NP-completo puede ser resuelto en tiempo polinómico, entonces cada problema NP-completo puede ser resuelto en tiempo polinómico, y cada problema en NP Puede ser resuelto en tiempo polinómico (es decir, P=NP). El ejemplo más famoso sería el problema de los vendedores ambulantes.
también existe un conjunto de problemas denominados NP-Duro de problemas., Estos problemas son al menos tan difíciles como los problemas NP, pero sin la condición que requiere que se resuelva en tiempo polinómico. Esto sugiere que los problemas NP-Hard pueden no ser necesariamente parte de la clase NP. Un ejemplo sería resolver un tablero de ajedrez-dado un estado de un tablero de ajedrez, es casi imposible decir si un movimiento dado en el estado dado, es de hecho el movimiento óptimo. Formalmente, no existe un algoritmo de tiempo polinómico para verificar una solución a un problema NP-Hard.,
si ponemos los dos juntos, un problema NP-completo implica que es NP-duro, pero un problema NP-duro no implica que es NP-completo.
definiendo NP-completitud
un problema L, es NP-completo si:
- l es NP-duro
- l pertenece a NP
El diagrama de abajo (enfoque en el lado izquierdo) debería aclarar las cosas.,
Wait, what does it mean by reducing A to B?
Reduction forms the crux of NP-Completeness.,
informalmente, un problema L1 se puede reducir a otro problema L2 si:
- cualquier instancia de L1 se puede modelar como una instancia de L2
- La solución a este último proporciona una solución al primero y viceversa
para entender esto intuitivamente, uno puede pensar en ello como tal:
si L1 es reducible a L2, L1 debe ser como máximo tan duro como L2. Por el contrario, L2 debe ser al menos tan duro como L1.
matemáticamente, esto se denota como: L1 ≤p L2 (léase como «L1 es polinomialmente reducible a L2»).,
