P, NP and What NP-Complete Means
P holds the problems solvable in polynomial time and NP the ones whose proposed answers can be checked that fast. NP-complete problems are the hardest in NP: every other NP problem reduces to them, so a fast method for one would be a fast method for all.
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
Some problems split into two questions: how hard is it to find an answer, and how hard is it to check one. P holds the problems you can solve in polynomial time, meaning the work grows manageably as the input grows. NP holds the problems where a proposed answer can be checked in polynomial time, even if finding it is slow. Checking can be easy while solving stays hard.
Take coloring a map with three colors so that neighbors always differ. The coloring itself is the certificate for a yes answer. To check it, you walk every shared border and confirm the two sides differ. That walk stays quick even for a big map, which is exactly what membership in NP asks for.
A reduction translates one problem into another in polynomial time, so a fast solver for the second problem would solve the first one too. An NP-complete problem sits inside NP, and every other NP problem reduces to it. That is why one polynomial algorithm for a single NP-complete problem would make all of NP solvable in polynomial time.
NP-hard and NP-complete are not the same claim. NP-hard means at least as hard as the hardest problems in NP. NP-complete adds membership: the problem is in NP too. If no quick check exists for its answers, call it NP-hard and stop there.
P means quick to solve, NP means quick to check, and NP-complete means in NP with every NP problem reducing to it.
2 · Watch
Take it off screen
Where it sits
Learn first
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.