P, NP, and NP-Completeness

Every algorithm this unit has built runs in polynomial time — but not every problem admits one. This note formalises the classes P (efficiently solvable) and NP (efficiently verifiable), defines polynomial-time reducibility as the tool for comparing problems' difficulty, and states what an NP-completeness proof actually establishes: that a problem is, in a precise sense, at least as hard as every other problem in NP — so that finding a polynomial algorithm for even one NP-complete problem would yield one for all of them (and finding a proof that none exists would prove none exists for any of them). This is the formal version of the "know when to stop optimising" discipline this unit's own staging notes name as the final skill this material aims to build.