Score:1

ZK: การทำซ้ำเพื่อลดความน่าจะเป็นของการหยุดจำลอง

ธง gd

ฉันกำลังพยายาม autodidact เพื่ออ่านบทที่ 4 ของ Foundation of Cryptography โดย Oded Goldreich (เพื่อให้คุณ "ปรับแต่ง" คำตอบของคุณ ฉันมีพื้นฐานด้านวิศวกรรม)

ถ้าฉันเข้าใจถูกต้อง ให้จำลองที่สมบูรณ์แบบ $S_1$ ความเป็นไปได้ที่จะหยุดไม่ใช่ปัญหาเพราะเราสามารถกำหนดตัวจำลองได้ $S_2$ ซึ่งทำซ้ำ $S_1$ สมมติว่า $n$ ครั้ง แสดงผลของการไม่หยุดครั้งแรก $S_1$ การวนซ้ำหรือผลลัพธ์ "จำลอง" หากทั้งหมด $S_1$ การทำซ้ำหยุดลง วิธีนี้น่าจะเป็นของ $S_2$ การแสดงผลจำลองสามารถลดลงได้ตามชอบด้วยการเติบโตของ $n$.

$S_1$ ความน่าจะเป็นของการหยุดชะงักอยู่เหนือขอบเขตโดย $1/2$แต่ทำไม? สำหรับฉันแล้วดูเหมือนว่าทุกๆ $S_1$ หยุดความน่าจะเป็น $<1$ จะลดลงไปทาง $0$ โดยใหญ่พอสมควร $n$. ยิ่งไปกว่านั้น ตัวจำลองหนึ่งดูเหมือนจะเป็นข้อโต้แย้งที่แตกต่างกันมากจากความน่าจะเป็นของความสมบูรณ์/ความสมบูรณ์ ที่ซึ่งเข้มงวด $1/2$ เกณฑ์ได้รับการพิสูจน์โดยกฎเสียงข้างมากที่ใช้กับกลยุทธ์การทำซ้ำ (ที่แตกต่างกัน) นั้น

และ btw มีเหตุผลใดที่ต้องเลือก $S_1$ ค่าการทำซ้ำ $n$ ให้เหมือนกับจำนวนการทำซ้ำอื่นๆ ที่จำเป็นในการเปลี่ยนจากความสมบูรณ์/ความสมบูรณ์ที่อ่อนแอไปสู่จำนวนที่แข็งแรงกว่า? หรือจำนวนของการวนซ้ำทั้งสองประเภทเป็นอิสระต่อกัน? ฉันเดาว่าข้อสงสัยนี้มาจากการที่ฉันสับสนว่า $S_2$ เป็นตัวจำลองสำหรับ IP ที่อ่อนแอ หรือสำหรับ IP ที่แรงกว่า...

ขอบคุณ!

Geoffroy Couteau avatar
cn flag
คุณพูดถูก ไม่มีอะไรเฉพาะเจาะจงเกี่ยวกับ 1/2: ค่าคงที่ใดๆ ที่อยู่ห่างจาก 1 จะเป็นการหลอกลวง
Geoffroy Couteau avatar
cn flag
และไม่ ไม่มีอะไรบังคับให้ $n$ สองตัวเหมือนกัน พวกมันเป็นปริมาณที่แตกต่างกันสองค่า ประเด็นในแต่ละครั้งมักจะเป็น "เราทำให้ความน่าจะเป็นที่จะทำลายความสมบูรณ์ / ความน่าจะเป็นที่จะล้มเหลวในการแยกข้อมูลมีน้อยมาก" แต่การทำซ้ำของการพิสูจน์เชิงโต้ตอบกับการใช้เครื่องจำลองซ้ำ ๆ นั้นแตกต่างกัน
baro77 avatar
gd flag
ขอบคุณ @GeoffroyCouteau ! เลยสงสัยว่าทำไม
Geoffroy Couteau avatar
cn flag
ฉันคิดว่ามันเป็นไปตามอำเภอใจจริงๆ เหตุผลน่าจะเป็นเรื่องง่าย ๆ เช่น: n การเรียกใช้โปรแกรมจำลองให้ความน่าจะเป็น 1/2^n ของความล้มเหลว และเราเคยประมาณค่า "เล็ก" ในรูปของ 2^(-something)

โพสต์คำตอบ

คนส่วนใหญ่ไม่เข้าใจว่าการถามคำถามมากมายจะปลดล็อกการเรียนรู้และปรับปรุงความสัมพันธ์ระหว่างบุคคล ตัวอย่างเช่น ในการศึกษาของ Alison แม้ว่าผู้คนจะจำได้อย่างแม่นยำว่ามีคำถามกี่ข้อที่ถูกถามในการสนทนา แต่พวกเขาไม่เข้าใจความเชื่อมโยงระหว่างคำถามและความชอบ จากการศึกษาทั้ง 4 เรื่องที่ผู้เข้าร่วมมีส่วนร่วมในการสนทนาด้วยตนเองหรืออ่านบันทึกการสนทนาของผู้อื่น ผู้คนมักไม่ตระหนักว่าการถามคำถามจะมีอิทธิพลหรือมีอิทธิพลต่อระดับมิตรภาพระหว่างผู้สนทนา