P versus NP
Can every quickly verified problem be quickly solved?
The P versus NP problem is a major unsolved problem in theoretical computer science. It asks whether every decision problem for which a proposed positive answer can be quickly verified can also be quickly solved.
- field
- Theoretical computer science
- known_for
- Central unsolved problem in computational complexity theory
- related_classes
- P (polynomial time solvable) and NP (nondeterministic polynomial time verifiable)
Reader's Guide
The P versus NP problem is foundational to computational complexity theory, which studies the resources required during computation to solve a given problem. The class P consists of decision problems solvable on a deterministic sequential machine in polynomial time; the class NP consists of decision problems whose positive solutions are verifiable in polynomial time given the right information. Clearly P ⊆ NP, but whether P equals NP remains unknown. If P ≠ NP, which is widely believed, it would mean there are problems in NP that are harder to compute than to verify. A proof either way would have profound implications for mathematics, cryptography, algorithm research, artificial intelligence, game theory, multimedia processing, philosophy, economics, and many other fields. The concept of NP-completeness is useful in attacking the question: NP-complete problems are those that any other NP problem can be reduced to in polynomial time, and if any NP-complete problem is in P, then P = NP. The Boolean satisfiability problem (SAT) was the first natural problem proven to be NP-complete by the Cook–Levin theorem.
Did You Know?
- The problem asks whether every decision problem that can be quickly verified can also be quickly solved, where 'quickly' means in polynomial time.
More in Mathematical Logic And Computation 1-21
Spotted an error? Know more?
This is a living reference — every entry is fact-audited, and reader corrections feed straight into our audit queue. Suggest an edit · See this site's audit record