P, NP and an explicit hardness chain
What this concept is
P consists of decision problems solvable in polynomial time. NP consists of decision problems with polynomial-length yes-certificates checkable in polynomial time. NP-hard means every NP problem reduces to the target in polynomial time; NP-complete means both NP-hard and in NP.
Why it matters here
NP does not mean “not polynomial.” P is contained in NP. Whether P=NP is unresolved. NP-hardness is not a proof that every instance is difficult or that the problem is undecidable.
Concrete example
Take 3-SAT’s NP-completeness as a stated external theorem. For a 3-CNF formula with m clauses, make one vertex per literal occurrence; connect all pairs in each clause, and connect occurrences that are complementary literals. A satisfying assignment lets us choose a true literal from each clause, giving an independent set of size m. Conversely, such a set chooses exactly one per clause and no contradictory pair; assign those literals true and fill unassigned variables arbitrarily. Every clause is satisfied.
Common confusion / misconception
The gadget construction alone is not a proof: it needs both directions and a polynomial size bound. Certificates are for yes-instances; an efficient verifier does not imply an equally simple no-certificate scheme.
How to use it
There are at most 3m vertices and O(m²) edges. Thus 3-SAT≤pIndependent Set; combine with the previous lesson to get Vertex Cover NP-hardness. A cover can be verified in polynomial time, so its decision version is NP-complete. Minimum cover is an optimization problem; call it NP-hard, not a decision language in NP. This is an introductory reduction proof, not a proof of Cook–Levin.
Check yourself
Why does an independent set of size m choose one occurrence per clause rather than two from some clause?
Mini drill or application
Construct the graph for (a∨b∨c) AND (¬a∨b∨d). Exhibit consistent selections. Then replace the formula with (a∨a∨a) AND (¬a∨¬a∨¬a); explain why no independent set of size two exists.
Read this only if stuck
Use Erickson’s Algorithms and lecture notes for reductions and hardness, and the selective reading guide for the matching approximation. Full-book reading is not required.