P versus NP
About this app
Compare finding a clique with checking a certificate. Explore polynomial and exponential growth and the possible relationships between P, NP and NP-complete problems.
The millennium problem P = NP?
P is the class of problems that can be solved in polynomial time, such as sorting or shortest paths. NP contains the problems whose solution can be checked in polynomial time once it is presented. Every problem in P is also in NP. Whether, conversely, everything that is quick to check is also quick to solve is open: that is the question P = NP, one of the Clay Institute's seven millennium problems with a prize of one million dollars. NP-complete problems such as SAT or clique are the hardest in NP: a fast algorithm for one of them would solve them all.
What the app shows
Three scenes. In “Solving vs checking” brute-force search looks for a clique of size 3 to 5 in a graph with 6 to 14 nodes and tries every subset to do so, whereas checking a certificate takes only k(k−1)/2 edge tests. The growth scene compares n², n³, 2ⁿ and n! on a logarithmic time axis up to the age of the universe. The map shows P, NP and NP-complete with examples in the two possible worlds P ≠ NP and P = NP.
Try it yourself
Set the number of nodes and the clique size, let the search run and compare its counter with the checking steps. Click nodes yourself and have your certificate checked. In the growth scene switch on a computer that is 1000 times faster: for 2ⁿ this gains only about ten steps in n. On the map you switch between the two worlds.
Frequently asked questions
- What is P vs NP in simple terms?
- The question is: can every problem whose solution can be checked quickly also be solved quickly? “Quickly” means in polynomial time. Checking a Sudoku is easy; solving one seems much harder in general. Whether it really is harder, nobody knows.
- What does NP-complete mean?
- A problem is NP-complete if it is in NP and every other NP problem can be reduced to it in polynomial time. Examples are SAT, clique, Hamiltonian cycle and knapsack. If a polynomial algorithm were found for one of them, P would equal NP.
- Does NP mean “not polynomial”?
- No. NP stands for nondeterministic polynomial: a proposed solution can be checked in polynomial time. P is a subset of NP. Whether NP is strictly larger than P is the open question.
- What does the P vs NP app show?
- A clique search in which brute force competes with quick checking, a growth scene with 2ⁿ and n! against polynomials, and a map of complexity classes that switches between the worlds P ≠ NP and P = NP.
Subject: Computer science
More from Computer science
- Ackermann function
- Elevator simulator
- Binary workshop
- Binary versus linear search
- The Collatz problem
- Inside a CPU
- Swap the inside
- One frame in 16 milliseconds — how a game engine renders an image (3D)
A VisuApp by heyprof: interactive, free in your browser, no sign-up. What is a VisuApp? · All apps