P versus 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 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.
Sources
- 1989: Ephraim J. Borowski and Jonathan M. Borwein: Dictionary of Mathematics ... (previous) ... (next): P equals NP
- 2008: David Nelson: The Penguin Dictionary of Mathematics (4th ed.) ... (previous) ... (next): Millennium Prize problems
- 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$.