การพิสูจน์แบบตรวจสอบได้ด้วยความน่าจะเป็น

ในทฤษฎีความซับซ้อนในการคำนวณ (Computational Complexity Theory) การพิสูจน์แบบตรวจสอบได้ด้วยความน่าจะเป็น หรือ Probabilistically Checkable Proof (PCP) คือรูปแบบหนึ่งของการพิสูจน์ที่สามารถตรวจสอบความถูกต้องได้โดยใช้อัลกอริทึมแบบสุ่ม (Randomized Algorithm) ซึ่งใช้จำนวนบิตสุ่มในปริมาณที่จำกัด และอ่านข้อมูลเพียงบางส่วน (Bounded number of bits) ของตัวบทพิสูจน์ทั้งหมด

เป้าหมายของระบบ PCP คือการให้อัลกอริทึมผู้ตรวจสอบ (Verifier) ยอมรับการพิสูจน์ที่ถูกต้อง และปฏิเสธการพิสูจน์ที่ผิดพลาดด้วยความน่าจะเป็นที่สูงมาก ซึ่งแตกต่างจากการพิสูจน์แบบมาตรฐาน (Standard Proof หรือ Certificate) ที่ผู้ตรวจสอบต้องอ่านข้อมูลทั้งหมดเพื่อตัดสินใจ แต่ PCP ช่วยให้สามารถตรวจสอบความถูกต้องได้โดยการสุ่มอ่านข้อมูลเพียงไม่กี่บิตเท่านั้น

นิยามและกลไกการทำงาน

ระบบการพิสูจน์แบบตรวจสอบได้ด้วยความน่าจะเป็นสำหรับปัญหาการตัดสินใจ $L$ ประกอบด้วยสองส่วนหลักคือ ผู้พิสูจน์ (Prover) และ ผู้ตรวจสอบ (Verifier) โดยมีเงื่อนไขดังนี้:

• ความสมบูรณ์ (Completeness): หากข้อความนั้นเป็นจริง (x ∈ L) และผู้พิสูจน์ส่งบทพิสูจน์ $\pi$ ที่ถูกต้อง ผู้ตรวจสอบจะต้องยอมรับข้อความนั้นด้วยความน่าจะเป็นอย่างน้อย $c(n)$
• ความถูกต้อง (Soundness): หากข้อความนั้นเป็นเท็จ (x ∉ L) ไม่ว่าผู้พิสูจน์จะส่งบทพิสูจน์ $\pi$ ใดๆ มาก็ตาม ผู้ตรวจสอบจะต้องยอมรับข้อความนั้นด้วยความน่าจะเป็นไม่เกิน $s(n)$

ในทางเทคนิค ผู้ตรวจสอบจะเป็นเครื่องจักรทัวริงแบบออราเคิล (Oracle Turing Machine) ที่ทำงานในเวลาพหุนาม (Polynomial Time) โดยมีตัวชี้วัดความซับซ้อนสองประการคือ:

1. ความซับซ้อนของการสุ่ม (Randomness Complexity) $r(n)$: จำนวนบิตสุ่มสูงสุดที่ผู้ตรวจสอบใช้
2. ความซับซ้อนของการสอบถาม (Query Complexity) $q(n)$: จำนวนบิตสูงสุดที่ผู้ตรวจสอบอ่านจากบทพิสูจน์

ทฤษฎีบท PCP และความสำคัญ

ผลลัพธ์ที่สำคัญที่สุดในเรื่องนี้คือ ทฤษฎีบท PCP (PCP Theorem) ซึ่งระบุว่า:

PCP[O(log n), O(1)] = NP

ความหมายของทฤษฎีบทนี้คือ ปัญหาใดๆ ที่อยู่ในคลาส NP (ปัญหาที่สามารถตรวจสอบคำตอบได้ในเวลาพหุนาม) สามารถเปลี่ยนรูปแบบการพิสูจน์ให้เป็น PCP ที่ผู้ตรวจสอบใช้บิตสุ่มเพียงระดับลอการิทึม $O(\log n)$ และอ่านข้อมูลจากบทพิสูจน์เพียงจำนวนคงที่ $O(1)$ บิตเท่านั้น ซึ่งเป็นผลลัพธ์ที่น่าทึ่งเพราะแสดงให้เห็นว่าเราไม่จำเป็นต้องอ่านบทพิสูจน์ทั้งหมดเพื่อยืนยันความถูกต้อง

การประยุกต์ใช้และผลกระทบ

ทฤษฎี PCP ไม่ได้มีความสำคัญเพียงแค่ในเชิงทฤษฎีการคำนวณ แต่ยังมีผลกระทบอย่างกว้างขวางในด้านอื่นๆ ดังนี้:

• ความยากในการประมาณค่า (Hardness of Approximation): PCP ถูกนำมาใช้เพื่อพิสูจน์ว่าปัญหาการหาค่าที่เหมาะสมที่สุด (Optimization Problems) บางอย่างนั้น ไม่เพียงแต่ยากที่จะหาคำตอบที่ถูกต้องที่สุด แต่ยังยากที่จะหาคำตอบที่ ใกล้เคียง กับค่าที่ถูกต้องที่สุดด้วย
• วิทยาการรหัสลับ (Cryptography): แนวคิดการตรวจสอบข้อมูลบางส่วนเพื่อยืนยันความถูกต้องถูกนำไปใช้ในการสร้างระบบการพิสูจน์แบบสั้น (Succinct Non-interactive Arguments of Knowledge หรือ SNARKs) ซึ่งเป็นรากฐานของเทคโนโลยีความเป็นส่วนตัวในบล็อกเชน

ความสัมพันธ์กับคลาสความซับซ้อนอื่นๆ

เมื่อปรับเปลี่ยนพารามิเตอร์ของ $r(n)$ และ $q(n)$ คลาส PCP จะมีความสัมพันธ์กับคลาสความซับซ้อนมาตรฐาน ดังนี้: