CIRCUIT-SAT

Vi har: Et vilkårlig språk (problem) $L\in NP$

Vet: $x\in L$ kan verifiseres i Polynomisk tid (pga det er i NP).

Vi ønsker: Å redusere dette til CIRUIT-SAT

Hvordan: Vi simulerer trinnene i verifikasjonsalgoritmen, $A$, med kretser!

$$\downarrow$$

Da blir spørsmålet: Kan $A$ (for et eller annet sertifikat) svare 1?