P versus NP problema, em pleno polinomial versus não-determinísticos polinomiais problema, na complexidade computacional (um subcampo da teoria da ciência da computação e matemática), a questão de saber se todos os chamados problemas NP são, na verdade, P problemas. P problema é que pode ser resolvido em “tempo polinomial,” o que significa que um algoritmo existe para a sua solução, de tal forma que o número de passos do algoritmo é limitado por uma função polinomial de n, onde n corresponde ao comprimento da entrada para o problema., Assim, os problemas P são ditos ser fáceis, ou tractable. Um problema é chamado de NP se sua solução pode ser adivinhada e verificada em tempo polinomial, e não determinístico significa que nenhuma regra particular é seguida para fazer o palpite.os problemas de programação Linear são NP, pois o número de passos no método simplex, inventado em 1947 pelo matemático americano George Dantzig, cresce exponencialmente com o tamanho da entrada. No entanto, em 1979, o matemático russo Leonid Khachian descobriu um algoritmo de tempo polinomial-i.e.,, the number of computational steps grows as a power of the number of variables, rather than exponentially—thereby showing that linear programming problems are actually P. This discovery allowed the solution of formerly intratable problems.

a problem is NP-hard if an algorithm for its solution can be modified to solve any NP problem-or any P problem, for that matter, as p problems are a subset of NP problems. (Nem todos os problemas NP-difíceis são membros da classe de problemas NP, no entanto. Um problema que é NP e NP-hard é dito ser NP-completo., Assim, encontrar um algoritmo eficiente para qualquer problema NP-completo implica que um algoritmo eficiente pode ser encontrado para todos os problemas NP, uma vez que uma solução para qualquer problema que pertencem a esta classe pode ser transformado em uma solução para qualquer outro membro da classe., Em 1971, o cientista da computação norte-Americano Stephen Cook provou que o satisfiability problema (um problema de atribuição de valores às variáveis em uma fórmula em álgebra Booleana, tais que a afirmação é verdadeira) é NP-completo, que foi o primeiro problema apresentado para ser NP-completo e abriu o caminho para mostrar outros problemas que são membros da classe de problemas NP-completos. Um exemplo famoso de um problema NP-completo é o problema do caixeiro viajante, que tem amplas aplicações na otimização de horários de transporte., Não se sabe se algum algoritmo de tempo polinomial será encontrado para problemas NP-completos, e determinar se esses problemas são tratáveis ou intratáveis permanece uma das questões mais importantes na ciência da Computação Teórica. Tal descoberta provaria que P = NP = NP-completo e revolucionaria muitos campos na ciência da computação e matemática.

Por exemplo, a criptografia moderna baseia-se na suposição de que factoring o produto de dois grandes números primos não é P., Note que verificar o produto de dois números primos é fácil (tempo polinomial), mas computar os dois fatores primos é difícil. A descoberta de um algoritmo eficiente para fatorar números grandes quebraria os esquemas de criptografia mais modernos.