NP Problem — Definition, Formula & Examples
An NP problem is a decision problem whose solution, once found, can be verified in polynomial time by a deterministic Turing machine. The class NP includes many important problems for which no known fast algorithm exists, but a proposed answer can be checked quickly.
NP (nondeterministic polynomial time) is the class of decision problems for which a 'yes' instance has a certificate (proof) that can be verified by a deterministic Turing machine in time polynomial in the size of the input. Equivalently, NP is the class of problems solvable in polynomial time by a nondeterministic Turing machine.
How It Works
To show a problem is in NP, you need two things: a certificate (a candidate solution) and a polynomial-time verifier (an algorithm that checks the certificate). The certificate must be polynomially bounded in the length of the input. If someone hands you a proposed solution, you must be able to confirm it is correct in polynomial time. Being in NP says nothing about how hard it is to find the solution — only that checking one is efficient.
Example
Problem: Show that the Subset Sum problem is in NP: given the set S = {3, 7, 1, 8, 4} and target t = 12, verify whether a proposed subset sums to t.
Certificate: A certificate is a proposed subset. Suppose someone claims the subset {3, 1, 8} sums to 12.
Verification: Add the elements of the proposed subset and compare to the target.
Time analysis: The verification step requires at most n additions and one comparison, where n is the number of elements in S. This runs in O(n) time, which is polynomial.
Answer: The certificate {3, 1, 8} is verified in polynomial time, confirming that Subset Sum is in NP.
Why It Matters
The P vs. NP question — whether every problem whose solution can be verified quickly can also be solved quickly — is one of the most important open problems in mathematics and computer science, carrying a $1,000,000 Millennium Prize. Understanding NP is essential in algorithm design, cryptography, and computational complexity courses, because it defines the boundary between problems we can handle efficiently and those we likely cannot.
Common Mistakes
Mistake: Assuming NP means 'not polynomial' or that NP problems cannot be solved in polynomial time.
Correction: NP stands for 'nondeterministic polynomial time.' Every problem in P is also in NP, since a polynomial-time solution trivially provides a polynomial-time verification. Whether P = NP remains unknown.