P, NP, reductions and lower bounds

P contains decision problems solvable in polynomial time. NP contains decision problems whose yes answers have polynomial-size certificates verifiable in polynomial time; NP does not mean non-polynomial. P⊆NP, and whether P=NP remains open. NP-complete problems are both in NP and NP-hard. NP-hard problems need not belong to NP.

A polynomial reduction A≤pB transforms A into B. A fast B solver would solve A. To prove B hard, reduce a known hard A to B, not merely the reverse. Distinguish the TSP decision problem from minimum-tour optimisation.

NP-hard does not mean every instance is impossible. Small instances, special classes, parameterisation and branch-and-bound may work well. Pseudo-polynomial algorithms depend on numeric magnitude rather than binary input length. Undecidability is a separate issue: no algorithm decides every instance.

Keep the reduction direction straight

To prove a new problem X hard using SAT, transform a SAT instance into an X instance in polynomial time and prove SAT yes iff X yes. This is SAT≤pX. Showing only X≤pSAT does not prove X hard: easy problems can also reduce to SAT.

NP-completeness requires two obligations: membership in NP through polynomial certificate verification, and a reduction from a known NP-hard problem. Calling an optimisation problem NP-complete without naming its decision version is imprecise. Decision versions include a threshold, such as whether a tour of cost≤K exists.

Encoding matters. Unary encoding of numeric n has length n; binary encoding has length about log₂ n. An O(n) loop can therefore be exponential in binary input length. Always identify the input-length measure before assigning a complexity class.

Foundation: Contrast verifying and finding a Hamiltonian certificate. Intermediate: Define a threshold-based decision version of an optimisation problem. Advanced: Present a reduction’s mapping, polynomial construction cost and two-way correctness separately. P≠NP has not been proved; preserve its open status.

def verify_cycle(vertices,edges,cycle):
    return len(cycle)==len(vertices) and set(cycle)==set(vertices) and all((cycle[i],cycle[(i+1)%len(cycle)]) in edges for i in range(len(cycle)))
assert verify_cycle([0,1,2],{(0,1),(1,2),(2,0)},[0,1,2])