Visão Geral

1

A classe P é a classe de problemas que podem ser decididos em tempo polinomial por uma máquina de Turing determinística, e a classe NP é a classe de problemas em que, dada uma evidência (chamada Testemunha) de que a resposta é Sim, a validade da Testemunha pode ser julgada (isso é chamado de verificação) em tempo polinomial. Como os problemas decidíveis em tempo polinomial podem ser verificados em tempo polinomial, é claro que P⊆NP, mas não está claro se P é um subconjunto próprio de NP. Ainda não há prova, mas muitos pesquisadores acreditam que P≠NP. E a conjectura de que esta classe P e a classe NP não são iguais é chamada de "Conjectura P≠NP".