ฉันกำลังพยายาม 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 ที่แรงกว่า...
ขอบคุณ!