RecentlyOdds & Ends
now playing

P and NP (computer science)

P and NP are classes of problems in computer science.

NP problems are those with solutions that are easy to verify.

P problems are those with solutions that are easy to verify AND easy to solve.

P = NP, P != NP

P != NP, while unproven, is a widely-held belief that is foundational to modern cryptography.

  • Computers and Intractability: A Guide to the Theory of NP-Completeness - Garey & Johnson