P versus NP
(Redirected from P = NP)
Jump to navigation
Jump to search
Open Question
The class of problems for which an algorithm can find a solution in polynomial time is termed $P$.
The class of problems for which an algorithm can verify a solution in nondeterministic polynomial time is termed $NP$.
The $P$ versus $NP$ question is:
- Are all problems in $NP$ also in $P$?
Progress
Most mathematicians and computer scientists expect the answer to the question is: no, they are not.
However, there has been no proof one way or the other so far.
Also known as
The P versus NP problem is also known as P equals NP or P = NP.
Sources
- 1989: Ephraim J. Borowski and Jonathan M. Borwein: Dictionary of Mathematics ... (previous) ... (next): P equals NP
- 1998: David Nelson: The Penguin Dictionary of Mathematics (2nd ed.) ... (previous) ... (next): NP problem
- 2008: David Nelson: The Penguin Dictionary of Mathematics (4th ed.) ... (previous) ... (next): Millennium Prize problems
- 2008: David Nelson: The Penguin Dictionary of Mathematics (4th ed.) ... (previous) ... (next): NP problem
- 2014: Christopher Clapham and James Nicholson: The Concise Oxford Dictionary of Mathematics (5th ed.) ... (previous) ... (next): Millennium Prize problems
- 2014: Christopher Clapham and James Nicholson: The Concise Oxford Dictionary of Mathematics (5th ed.) ... (previous) ... (next): Appendix $18$: Millennium Prize problems: $1$.
- 2021: Richard Earl and James Nicholson: The Concise Oxford Dictionary of Mathematics (6th ed.) ... (previous) ... (next): Appendix $23$: Millennium Prize problems: $1$.