การคำนวณแบบสุ่มและการคำนวณเชิงโต้ตอบ

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

Definition

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

Scope

หัวข้อนี้ครอบคลุมคลาสความซับซ้อนเชิงความน่าจะเป็น รวมถึง BPP, RP และ ZPP และคำถามที่ว่าความสุ่มสามารถถูกกำจัดได้หรือไม่, ระบบการพิสูจน์เชิงโต้ตอบและทฤษฎีที่ระบุ IP ด้วย PSPACE, การพิสูจน์แบบความรู้เป็นศูนย์ (zero-knowledge proofs) และการพิสูจน์ที่ตรวจสอบได้เชิงความน่าจะเป็น (probabilistically checkable proofs) ซึ่งเป็นพื้นฐานของความยากของการประมาณค่า

Core questions

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

Key theories

IP เท่ากับ PSPACE

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

ทฤษฎี PCP

ทุกปัญหาใน NP มีการพิสูจน์ที่สามารถตรวจสอบได้โดยการอ่านเพียงจำนวนบิตที่สุ่มเลือกมาคงที่ ซึ่งเป็นผลลัพธ์ที่ระบุเกณฑ์ที่แน่นอนซึ่งเกินกว่านั้นการประมาณค่าปัญหาการปรับให้เหมาะสมหลายอย่างจะกลายเป็น NP-hard

Clinical relevance

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

History

การพิสูจน์เชิงโต้ตอบและการพิสูจน์แบบความรู้เป็นศูนย์ได้รับการแนะนำโดย Goldwasser, Micali และ Rackoff และโดย Babai ในช่วงกลางทศวรรษ 1980 Shamir พิสูจน์ว่า IP เท่ากับ PSPACE ในปี 1990 และทฤษฎี PCP ซึ่งเสร็จสมบูรณ์โดย Arora และคนอื่นๆ ในช่วงต้นทศวรรษ 1990 ได้ปฏิวัติการศึกษาการประมาณค่า ในขณะที่ข้อสันนิษฐานที่ว่าเวลาพหุนามแบบสุ่มเท่ากับเวลาพหุนามแบบกำหนด (randomized polynomial time equals deterministic polynomial time) ยังคงเป็นคำถามที่เปิดอยู่

Debates

ความสุ่มเพิ่มพลังการคำนวณที่แท้จริงหรือไม่?

ผลลัพธ์หลายอย่างชี้ให้เห็นว่า BPP เท่ากับ P ภายใต้ข้อสันนิษฐานความยากที่เป็นไปได้ ซึ่งหมายความว่าความสุ่มสามารถถูกกำจัดออกจากอัลกอริทึมที่มีประสิทธิภาพได้ในทางทฤษฎี การที่การลดความสุ่ม (derandomization) นี้จะคงอยู่โดยไม่มีเงื่อนไขหรือไม่นั้นยังไม่ได้รับการแก้ไข ทำให้ยังคงเป็นคำถามว่าความสุ่มมีความจำเป็นเพียงใด

Key figures

• Shafi Goldwasser
• Silvio Micali
• László Babai
• Adi Shamir

Seminal works

• aroraBarak2009
• goldreich2008

Frequently asked questions

การโยนเหรียญช่วยอัลกอริทึมได้อย่างไร?

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

การพิสูจน์แบบความรู้เป็นศูนย์คืออะไร?

เป็นโปรโตคอลเชิงโต้ตอบที่ทำให้ผู้ตรวจสอบมั่นใจว่าข้อความนั้นเป็นจริงโดยไม่เปิดเผยสิ่งใดนอกเหนือจากความจริงของมัน แม้แต่เหตุผลที่มันเป็นจริง การพิสูจน์ดังกล่าวช่วยให้ เช่น การพิสูจน์ว่าคุณรู้รหัสผ่านหรือความลับโดยไม่ต้องเปิดเผย และเป็นรากฐานของความเป็นส่วนตัวในการเข้ารหัสสมัยใหม่