NP-completeness combines verification and reduction hardness.
Key knowledge
A decision problem B is NP-hard when every problem in NP has a polynomial-time reduction to B. B is NP-complete when it is also in NP. A polynomial algorithm for any NP-complete problem would give polynomial algorithms for all NP problems.
Conditions and scope
Here reductions are polynomial-time many-one transformations preserving yes/no answers.
NP-hard problems need not themselves be in NP; hardness is a worst-case classification.
Sources · 1
References
Sources retain their recorded scope. A source link alone does not establish verification of every statement.
A decision problem B is NP-hard when every problem in NP has a polynomial-time reduction to B. B is NP-complete when it is also in NP. A polynomial algorithm for any NP-complete problem would give polynomial algorithms for all NP problems.
For a 3CNF formula with m clauses, make a vertex for each literal occurrence. Join occurrences from different clauses unless their literals are complementary. The formula is satisfiable exactly when the graph has a clique of size m: choose one true occurrence per clause; conversely the clique's consistent literals extend to an assignment.
Boolean satisfiability SAT is NP-complete under polynomial-time many-one reductions. For each language A∈NP and input x, a polynomial-size formula encodes a polynomial-time accepting computation tableau so that x∈A exactly when that formula is satisfiable; a satisfying assignment itself supplies the NP witness.
Introduce variables for Boolean subformula gates, constrain each gate to agree with its inputs using clauses of at most three literals, and require the output gate true. This constructs a linear-size equisatisfiable 3CNF formula, showing SAT≤ₚ3SAT and therefore 3SAT is NP-complete.
The PCP theorem expresses NP=PCP(O(log n),O(1)): a polynomial-time verifier uses logarithmically many random bits and queries a constant number of positions in a polynomial-length proof, with completeness one and bounded soundness such as one-half. Random access to the proof is part of the model. This is not a claim that an arbitrary written proof can be checked reliably by reading a few sentences without encoding it.