What is the seed (first) NP-complete problem, and how is it proven NP-hard?
What is the seed (first) NP-complete problem, and how is it proven NP-hard?
Answer
CIRCUIT-SAT. It is proven NP-hard directly (Cook): any NP verifier A running in T(n) steps is simulated by T(n) time-unrolled copies of the circuit for one computation step, with x hardwired and the certificate y as free input — the circuit is satisfiable iff x is a yes-instance.
A computer’s hardware is itself a boolean circuit, so any polynomial computation can be frozen into a polynomial-size circuit. This bootstraps the whole theory without needing a prior NP-complete problem.