P, NP and What NP-Complete Means
P contains decision problems solvable in polynomial time. NP contains decision problems whose yes answers have polynomial-length certificates checkable in polynomial time. NP-complete means both in NP and NP-hard. A polynomial algorithm for one NP-complete problem would imply P = NP.
What a learner can do afterwards
- Give a certificate for a yes-instance of a named NP problem and check it in polynomial time
- Explain what would follow if any single NP-complete problem had a polynomial algorithm
- Say why NP-hard and NP-complete are not the same claim
1 · Read
P contains yes-or-no decision problems with a deterministic algorithm whose worst-case runtime is bounded by a fixed polynomial in input length n. A bound c times n^k uses constants c and k independent of the input. Polynomial time need not be practical: large constants or powers can still be costly. Fast runs on selected inputs do not establish a polynomial worst-case bound.
NP contains decision problems whose yes answers have polynomial-length certificates checked in polynomial time. A yes input has at least one accepted certificate; a no input has none. Every problem in P is also in NP. Whether P equals NP is open. Failure to find a polynomial verifier does not prove that none exists.
For three-color map coloring, ask whether each region can receive red, green or blue with different colors across every shared border. A certificate lists one allowed color per region. Check the color list and every border. With V regions and E borders in an adjacency-list representation, checking takes O(V + E) time. A rejected coloring does not rule out another valid coloring.
A problem is NP-hard if every problem in NP has an answer-preserving polynomial-time reduction to it. It is NP-complete if it is also in NP. NP-hardness alone neither establishes NP membership nor excludes it. To claim NP-completeness, prove both the reductions and polynomial certificate verification.
You have seen how reductions reuse a target solver. Every NP problem reduces to any NP-complete problem. A polynomial-time algorithm for one NP-complete problem would therefore put all of NP in P. Since P is already contained in NP, this would prove P = NP. It would not automatically make every implementation practical.
P has polynomial-time decision algorithms. NP has polynomially checkable short yes certificates. NP-complete means in NP and NP-hard. Whether P = NP is open.
Original lesson, questions and flashcards written for this learning dataset.
Checking answers and choosing a search is an original reading written for this learning dataset.
More to read
Checking answers and choosing a search
A certificate gives a verifier something specific to test. For three-color map coloring, it supplies one allowed color per region. The verifier checks those colors and every shared border. Rejecting one coloring does not reject all possible colorings.
NP requires polynomial-length yes certificates and polynomial-time verification. P requires a deterministic polynomial-time decision algorithm. P is contained in NP; whether they are equal remains open. A polynomial bound can still involve large constants or a large power, so it is not a promise of a short wait.
A heuristic guides choices during a computation. An exact SAT solver may use one to select its next variable while keeping a complete search. An optimization procedure may instead stop with a candidate that is not proved best. The word heuristic alone guarantees neither a good answer nor a short runtime. Correctness and answer quality need their own arguments.
Superpolynomial growth need not double whenever input length increases by one. Exponential growth is one kind of superpolynomial growth. A slow method does not prove every method slow, and successful test runs do not establish a polynomial worst-case bound. These distinctions matter when comparing practical search with NP-completeness.
2 · Watch
Take it off screen
Where it sits
Optional connections
8 questions wait behind this lesson, each with its answer explained. Every answer feeds the sky: stars light as they are learned, and dim when it is time to come back.