Resumen

1

La clase P es la clase de problemas que pueden ser resueltos en tiempo polinómico por una máquina de Turing determinista, y la clase NP es la clase de problemas para los cuales, cuando se da una prueba de que la respuesta es afirmativa (llamada testigo), la validez del testigo puede ser verificada en tiempo polinómico (esto se llama verificación). Dado que los problemas que se pueden resolver en tiempo polinómico también se pueden verificar en tiempo polinómico, es evidente que P⊆NP, pero no está claro si P es un subconjunto propio de NP o no. Aunque todavía no hay pruebas, muchos investigadores creen que P≠NP. La conjetura de que la clase P y la clase NP no son iguales se llama "Conjetura P≠NP".