p versus NP problem, en polinomio completo versus polinomio no determinista problem, en complejidad computacional (un subcampo de la informática teórica y las matemáticas), la cuestión de si todos los llamados problemas NP son en realidad problemas P. Un problema P es uno que se puede resolver en «tiempo polinómico», lo que significa que existe un algoritmo para su solución tal que el número de pasos en el algoritmo está limitado por una función polinómica de n, donde n corresponde a la longitud de la entrada para el problema., Por lo tanto, se dice que los problemas P son fáciles o tratables. Un problema se llama NP si su solución se puede adivinar y verificar en tiempo polinómico, y no determinista significa que no se sigue ninguna regla particular para hacer la conjetura.

los problemas de programación lineal son NP, ya que el número de pasos en el método simplex, inventado en 1947 por el matemático estadounidense George Dantzig, crece exponencialmente con el tamaño de la entrada. Sin embargo, en 1979 el matemático ruso Leonid Khachian descubrió un algoritmo de tiempo polinómico—i. e.,, el número de pasos computacionales crece como una potencia del número de variables, en lugar de exponencialmente, lo que demuestra que los problemas de programación lineal son en realidad P. este descubrimiento permitió la solución de problemas anteriormente intratables.

un problema es NP-hard si un algoritmo para su solución puede ser modificado para resolver cualquier problema NP—o cualquier problema P, para el caso, ya que los problemas P son un subconjunto de problemas NP. (Sin embargo, no todos los problemas NP-hard son miembros de la clase de problemas NP.) Un problema que es tanto NP como NP-hard se dice que es NP-completo., Por lo tanto, encontrar un algoritmo eficiente para cualquier problema NP-completo implica que se puede encontrar un algoritmo eficiente para todos los problemas NP, ya que una solución para cualquier problema perteneciente a esta clase puede ser refundida en una solución para cualquier otro miembro de la clase., En 1971, el científico estadounidense Stephen Cook demostró que el problema de satisfactibilidad (un problema de asignar valores a variables en una fórmula en álgebra booleana de tal manera que la declaración es verdadera) es NP-completo, que fue el primer problema que se demostró que era NP-completo y abrió el camino para mostrar otros problemas que son miembros de la clase de problemas NP-completos. Un ejemplo famoso de un problema NP-completo es el problema del vendedor ambulante, que tiene amplias aplicaciones en la optimización de los horarios de transporte., No se sabe si se encontrarán algoritmos de tiempo polinómico para problemas NP completos, y determinar si estos problemas son tratables o intratables sigue siendo una de las preguntas más importantes en la informática teórica. Tal descubrimiento demostraría que P = NP = NP-completa y revoluciona muchos campos de la informática y las matemáticas.

por ejemplo, la criptografía moderna se basa en la suposición de que factorizar el producto de dos números primos grandes no es P., Tenga en cuenta que verificar el producto de dos números primos es fácil (tiempo polinómico), pero calcular los dos factores primos es difícil. El descubrimiento de un algoritmo eficiente para factorizar grandes números rompería la mayoría de los esquemas de cifrado modernos.

en 2000 el matemático estadounidense Stephen Smale ideó una influyente lista de 18 problemas matemáticos importantes para resolver en el siglo XXI. El tercer problema en su lista era el problema de P contra NP., También en 2000 fue designado un problema del Milenio, uno de los siete problemas matemáticos seleccionados por el Instituto de matemáticas de arcilla de Cambridge, Massachusetts, EE.UU., para un premio especial. La solución para cada problema del Milenio vale 1 millón de dólares.