TOPICS
Search

P Versus NP Problem


The P versus NP problem is the determination of whether all NP-problems are actually P-problems. If P and NP are not equivalent, then the solution of NP-problems requires (in the worst case) an exhaustive search, while if they are, then asymptotically faster algorithms may exist.

The answer is not currently known, but determination of the status of this question would have dramatic consequences for the potential speed with which many difficult and important problems could be solved.

In the Season 1 episode "Uncertainty Principle" (2005) of the television crime drama NUMB3RS, math genius Charlie Eppes uses the game minesweeper as an analogy for the P vs. NP problem.


See also

Complexity Theory, NP-Problem, P-Problem

Explore with Wolfram|Alpha

References

Borwein, J. and Bailey, D. Mathematics by Experiment: Plausible Reasoning in the 21st Century. Wellesley, MA: A K Peters, pp. 4-5, 2003.

Cite this as:

Weisstein, Eric W. "P Versus NP Problem." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/PVersusNPProblem.html

Subject classifications