ทฤษฎีบทมาตรฐานคือความพึงพอใจของวงจรบูลีนคือ NP-complete (แสดงใน ซีแอลอาร์เอส, ตัวอย่างเช่น).
ฉันสนใจว่าข้อความเหล่านี้มีความหมายอย่างเป็นทางการอย่างไร
จาก CLRS ฉันสามารถอ้างอิงได้
$$\text{CIRCUIT-SAT} = \{C \mid \text{$C$ เป็นวงจรรวมบูลีนที่น่าพอใจ}\}$$
ใน Bitansky และคณะ, ความพึงพอใจของวงจรบูลีนใช้เพื่อจับข้อความที่จะพิสูจน์
อย่างไรก็ตาม นี่ไม่ใช่ CIRCUIT-SAT: Bitansky และคณะ พิจารณาความพอใจของวงจร $C$ สำหรับ หนึ่ง ป้อนข้อมูล $x$. CIRCUIT-SAT อธิบายถึงความพึงพอใจของวงจรเท่านั้น $C$ สำหรับ ใดๆ ป้อนข้อมูล $x$.
zk-SNARK พิสูจน์ข้อความ $x \ใน L$ สำหรับ $L \ใน NP$.
สิ่งที่ทำเพื่อสร้าง zk-SNARK สำหรับความพึงพอใจของวงจรบูลีนคือการลด $L$ ไปยังวงจรบูลีน $C$ ดังนั้น $C$ เป็นที่น่าพอใจ สำหรับการป้อนข้อมูล $x$ ถ้า $x \ใน L$. $C$ โมเดล $L$เพื่อที่จะพูด
ฉันสับสนที่มีคนพูดว่าวงจรบูลีน (หรือเลขคณิต) นั้นสมบูรณ์ NP ตามที่ผมเข้าใจคือ $L$ จำเป็นต้องสร้างแบบจำลองโดยวงจร $C$. แต่ถ้าว่ากันตามนิยามของ CIRCUIT-SAT $x$ จะต้องแปลงเป็นวงจร $C$.
CIRCUIT-SAT สำหรับ zk-SNARK ควรมีลักษณะอย่างไร
$$\text{CIRCUIT-SAT} = \{ (C, x) \mid \text{$C$ เป็นวงจรรวมบูลีนที่น่าพอใจสำหรับอินพุต $x$}\}$$
เราอยากได้วงจร ต่อภาษาไม่ใช่ต่ออินพุต
ดังนั้น เมื่อมีคนพูดว่าความน่าพึงพอใจของวงจร R1CS, QSPs หรือ QAPs นั้นเป็น NP-complete ในบริบทของ zk-SNARK พวกเขาหมายถึงคำจำกัดความของฉันเกี่ยวกับ CIRCUIT-SAT และคำที่คล้ายกันหรือไม่