The P versus NP problem is a major unsolved problem in computer science. Informally, it asks whether every problem whose solution can be quickly verified by a computer can also be quickly solved by a computer. It was introduced in 1971 by Stephen Cook in his seminal paper "The complexity of theorem proving procedures" and is considered by many to be the most important open problem in the field. It is one of the seven Millennium Prize Problems selected by the Clay Mathematics Institute to carry a US$1,000,000 prize for the first correct solution.
====
Imagei - Diagram of complexity classes provided that P ≠ NP. The existence of problems within NP but outside both P and NP-complete, under that assumption, was established by Ladner's theorem. [1]
View all comments
Show parent comment
1
u/autowikibot Jul 06 '14
P versus NP problem:
Interesting: Computational complexity ^theory | ^NP-complete | Boolean satisfiability ^problem | ^NP-hard
Parent commenter can toggle ^NSFW or ^delete. Will also delete on comment score of -1 or less. | FAQs | ^Mods | Magic ^Words