Historia Wcześniejsze intuicje podobnych trudności pojawiały się jeszcze przed formalnym zdefiniowaniem klas P i NP. W 1955 roku John Nash w liście do National Security Agency rozważał zależność między długością klucza kryptograficznego a trudnością jego złamania. Rok później Kurt Gödel pytał Johna von Neumanna o możliwość szybkiego rozstrzygania problemów dowodzenia twierdzeń. Później zwracano uwagę, że list ten zapowiadał część motywacji stojących za problemem P versus NP.

Pierwszym naturalnym problemem, dla którego wykazano NP-zupełność, był problem spełnialności formuł logicznych. Wynik ten, znany jako twierdzenie Cooka-Levina, został sformułowany przez Stephena Cooka w 1971 roku, a niezależnie w pokrewnej postaci przez Leonida Levina. W 1972 roku Richard Karp pokazał metodę sprowadzania SAT do wielu innych problemów kombinatorycznych i wyodrębnił 21 klasycznych problemów NP-zupełnych, co utrwaliło redukcje wielomianowe jako podstawowe narzędzie badania P vs NP.