P versus NP

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$.