O teoremă standard este că satisfacabilitatea circuitului boolean este NP-complet (arată în CLRS, de exemplu).
Sunt interesat de ceea ce înseamnă oficial aceste afirmații.
De la CLRS, pot să citez asta
$$\text{CIRCUIT-SAT} = \{C \mid \text{$C$ este un circuit combinațional boolean satisfacabil}\}$$
În Bitansky și colab., satisfacabilitatea circuitului boolean este folosită pentru a capta declarația de demonstrat.
Cu toate acestea, acesta nu este CIRCUIT-SAT: Bitansky et al. luați în considerare satisfacabilitatea unui circuit $C$ pentru un intrare $x$. CIRCUIT-SAT descrie doar satisfacabilitatea unui circuit $C$ pentru orice intrare $x$.
Un zk-SNARK dovedește afirmațiile $x \în L$ pentru $L \în NP$.
Ceea ce se face pentru a crea un zk-SNARK pentru satisfacabilitatea circuitului boolean este reducerea $L$ la un circuit boolean $C$ astfel încât $C$ este satisfăcătoare pentru o intrare $x$ dacă $x \în L$. $C$ modele $L$, ca sa zicem asa.
Sunt confuz de oamenii care spun că satisfacabilitatea circuitului boolean (sau aritmetic) este NP-complet. După cum am înțeles eu, $L$ trebuie modelat de un circuit $C$. Totuși, dacă am urmat definiția CIRCUIT-SAT, $x$ ar trebui convertit într-un circuit $C$.
Cum ar trebui să arate CIRCUIT-SAT pentru zk-SNARK
$$\text{CIRCUIT-SAT} = \{ (C, x) \mid \text{$C$ este un circuit combinațional boolean satisfacabil pentru intrarea $x$}\}$$
Vrem un circuit pe limbă, nu pe intrare.
Deci, când cineva spune că satisfacabilitatea circuitelor, R1CS, QSP-uri sau QAP-uri este NP-completă în contextul zk-SNARK-urilor, se referă de fapt la definiția mea de CIRCUIT-SAT și altele similare?
