ใน CGPR (เชื่อมโยงไปยังกระดาษ) ข้อ 3.5 ระบุว่าค่าใช้จ่ายในการพิสูจน์คือ $O(|C| \log(|C|))$กำหนดให้ขนาดของวงจรคือ $|ค|$.
สำหรับฉันแล้วดูเหมือนว่าระดับพหุนามใน QAP ที่เป็นผลลัพธ์ควรเป็น $O(|C|)$. จะไม่มีค่าใช้จ่ายในการพิสูจน์ $O(|C|)$? ฉันพลาดบางขั้นตอนที่นี่หรือไม่
ประเด็นสำคัญคือพวกเขาใช้วงจรสากลที่นั่น:
เมื่อเราสร้าง SNARK สำหรับวงจร SAT เราใช้ QSP สำหรับ วงจรสากลซึ่งมีขนาด $O(|C| \log |C|)$ ที่ไหน $|ค|$ คือขนาดสูงสุดของวงจรในโจทย์ความพอใจ
วงจรสากลเป็นวงจรที่สามารถคำนวณวงจรอื่นได้ ลักษณะทั่วไปนี้เป็นที่มาของปัจจัยลอการิทึมเพิ่มเติม ซึ่งจะอธิบายไว้ในตอนต้นของส่วนที่ 3:
เทียบตรงๆกับ Groth ก็พอไหวครับ $u$ เป็นวงจรที่เลือกใช้โดยการสร้าง $R$ [(ความสัมพันธ์)] จาก ก วงจรสากล ในกรณีนี้ขนาดของวงจรคอมพิวเตอร์ $R$ อาจมีขนาดใหญ่ขึ้น กว่า $|u|$ โดยปัจจัยลอการิทึมซึ่งจะเพิ่มขนาด CRS และการคำนวณการพิสูจน์ตามลำดับ $\tilde{O}(|u|)$. ถ้า $u$ ... สามารถเลือกแบบไม่ปรับเปลี่ยนได้ โครงร่างของเราจะมีประสิทธิภาพมากขึ้น
เดอะ $\tilde{O}$ สัญกรณ์ซ่อนปัจจัยลอการิทึม ในตอนท้ายกล่าวถึงการรู้วงจรเฉพาะ $u$ จะมีประสิทธิภาพมากขึ้น - นี่คือสิ่งที่คุณมีในใจ เหตุผลสำหรับความถูกต้องของการปรับตัวเป็นเพราะสิ่งนี้จำลองได้ถูกต้องมากขึ้นว่าโปรโตคอลน่าจะใช้ในสถานการณ์จริงอย่างไร - บ่อยครั้งที่คุณคาดหวังให้ผู้พิสูจน์เห็น CRS ก่อนเริ่มการพิสูจน์ ดังนั้นพวกเขาจึงสามารถเลือกข้อความที่ต้องการได้ (อาจจะผิดพลาด) พยายามพิสูจน์ตาม CRS (แบบปรับตัว)
กระดาษแผ่นนี้ อธิบายการสร้างวงจรสากลที่มีประสิทธิภาพ และให้คำอธิบายว่าวงจรดังกล่าวทำงานอย่างไรในเบื้องต้น (ตัวอย่าง ดูหน้า 4-7) โดยสัญชาตญาณ ปัจจัยลอการิทึมถูกนำมาใช้เพราะวงจรเหล่านี้มีแนวโน้มที่จะสร้างซ้ำ โดยแต่ละปัญหาย่อยมีขนาดประมาณครึ่งหนึ่ง เราจึงมีปัจจัยล็อกปกติที่เราได้รับเมื่อจัดการกับไบนารีทรี สำหรับคำอธิบายที่ดีกว่า ฉันคิดว่ากระดาษเป็นสิ่งที่ดีที่สุดในการอ่าน
คนส่วนใหญ่ไม่เข้าใจว่าการถามคำถามมากมายจะปลดล็อกการเรียนรู้และปรับปรุงความสัมพันธ์ระหว่างบุคคล ตัวอย่างเช่น ในการศึกษาของ Alison แม้ว่าผู้คนจะจำได้อย่างแม่นยำว่ามีคำถามกี่ข้อที่ถูกถามในการสนทนา แต่พวกเขาไม่เข้าใจความเชื่อมโยงระหว่างคำถามและความชอบ จากการศึกษาทั้ง 4 เรื่องที่ผู้เข้าร่วมมีส่วนร่วมในการสนทนาด้วยตนเองหรืออ่านบันทึกการสนทนาของผู้อื่น ผู้คนมักไม่ตระหนักว่าการถามคำถามจะมีอิทธิพลหรือมีอิทธิพลต่อระดับมิตรภาพระหว่างผู้สนทนา
