A topic in the Open Knowledge Graph — a free, open map of 15,290 topics and the order to learn them in.
NP is the class of decision problems solvable by a nondeterministic TM in polynomial time, equivalently the problems whose solutions can be *verified* in polynomial time given a certificate (witness). The two definitions are equivalent: a nondeterministic TM 'guesses' a certificate and verifies it. NP contains P (any polynomial-time solution is also a polynomial-time certificate) and includes many natural combinatorial problems: satisfiability, Hamiltonian path, graph coloring, and subset sum. Whether NP equals P is the most famous open problem in mathematics.
For each NP problem, identify the certificate explicitly (e.g., for 3-SAT: a satisfying assignment; for Hamiltonian path: the path itself) and verify it checks in polynomial time. This grounds the abstract definition in concrete examples.
You already know that time complexity classes group decision problems by how quickly a deterministic Turing machine can solve them — P captures the problems solvable in polynomial time. NP extends this idea by asking a different question: instead of "can we solve this quickly?", it asks "can we check a proposed answer quickly?" The name stands for nondeterministic polynomial time, not "non-polynomial," and the distinction matters. A nondeterministic Turing machine can be thought of as one that magically guesses the right answer and then verifies it in polynomial time. The class NP is exactly the set of problems where this guess-then-verify strategy works.
The most concrete way to understand NP is through the certificate-verifier definition. For any problem in NP, there exists a short proof — called a certificate or witness — that a "yes" answer is correct, and a polynomial-time algorithm (the verifier) that checks it. Consider the Boolean satisfiability problem (SAT): given a formula, is there an assignment of variables that makes it true? If someone hands you a specific assignment (the certificate), you can plug in the values and check the formula in polynomial time. You don't need to search through all possible assignments — you just need to verify the one you're given. Similarly, for the Hamiltonian path problem, the certificate is the path itself; checking that it visits every vertex exactly once is straightforward.
Every problem in P is automatically in NP, because if you can solve a problem in polynomial time, you can certainly verify a solution in polynomial time — just solve it from scratch and compare. The deep question is whether the reverse holds: are there problems in NP that are not in P? This is the P vs NP problem, the most celebrated open question in theoretical computer science. If P = NP, then every problem whose solutions are easy to check would also be easy to solve — a stunning collapse that would transform cryptography, optimization, and artificial intelligence. If P ≠ NP, as most researchers suspect, then there is a fundamental asymmetry between finding solutions and verifying them.
What makes NP so important is that it captures a huge number of practical problems. Scheduling, routing, graph coloring, protein folding, circuit design — all have natural NP formulations. When you encounter a new combinatorial problem, the first structural question is: can I define a polynomial-size certificate and a polynomial-time verifier? If yes, the problem is in NP. From your work with nondeterministic finite automata, you already have intuition for nondeterminism as "exploring all paths at once." NP lifts that same idea to polynomial-time computation: the nondeterministic TM explores all possible certificates simultaneously, and if any branch accepts, the machine accepts. The equivalence between this branching model and the certificate-verifier definition is what gives NP its theoretical power and practical reach.