P vs NP se može jednostavno opisati kao problem da li postoji pitanje čiji odgovor može biti brzo proveren, ali koji zahteva nemoguće dugo vremena da bi se rešilo bilo kojom direktnom procedurom. Pogledati na primer
http://www.claymath.org/millennium/P_vs_NP/).
Stephen Cook i Leonid Levin su formulisali P (t.j., lako za pronaći) vs NP (t.j., lako za proveriti) problem nezavisno 1971. god.
U knjizi M. 2ivkovića “Agoritmi” ćete takodje pronaći pojednostavljenu formulaciju tog problema pa vam može poslužiti za uvod uz napomenu da je materija tako izložena da morate biti upoznati sa pojmovima kao što su složenost algoritma, Tjuringova mašina, deterministička Tjuringova mašina i slično.