~/ learn/ comp-372/ cards/ NP-complete problems & how to prove one
1 of 6

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.

space flip · ← → navigate · esc to exit
NORMAL ~/memra/library/50b0ebf0-80e0-444e-9070-6a0a1607ea20/flashcard utf-8 LF