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

การพิสูจน์ที่ตรวจสอบได้ด้วยความน่าจะเป็นก่อให้เกิดคลาสความซับซ้อนมากมายขึ้นอยู่กับจำนวนคำถามที่ต้องการและปริมาณของความสุ่มที่ใช้ คลาสPCP [ r ( n ), q ( n )]หมายถึงเซตของปัญหาการตัดสินใจที่มีการพิสูจน์ที่ตรวจสอบได้ด้วยความน่าจะเป็นซึ่งสามารถตรวจสอบได้ในเวลาพหุนามโดยใช้บิตสุ่มไม่เกินr ( n ) บิตและโดยการอ่าน บิตของการพิสูจน์ไม่เกินq ( n ) บิต ^{[ 1 ]}เว้นแต่จะระบุไว้เป็นอย่างอื่น การพิสูจน์ที่ถูกต้องควรได้รับการยอมรับเสมอ และการพิสูจน์ที่ไม่ถูกต้องควรถูกปฏิเสธด้วยความน่าจะเป็นมากกว่า 1/2 ทฤษฎีบท PCPซึ่งเป็นผลลัพธ์สำคัญในทฤษฎีความซับซ้อนของการคำนวณ ระบุว่าPCP [ O ( log n ), O (1)] = NP

กำหนดให้ปัญหาการตัดสินใจL ( ภาษา บนตัวอักษร Σ) ระบบพิสูจน์ที่ตรวจสอบได้เชิงความน่าจะเป็นสำหรับLที่มีความสมบูรณ์c ( n ) และความถูกต้องs ( n ) โดยที่0 ≤ s ( n ) ≤ c ( n ) ≤ 1ประกอบด้วยผู้พิสูจน์และผู้ตรวจสอบ เมื่อกำหนดคำตอบที่อ้างว่าxที่มีความยาวnซึ่งอาจเป็นเท็จ ผู้พิสูจน์จะสร้างการพิสูจน์πซึ่งระบุว่าxแก้ปัญหาL ได้ ( x ∈ Lการพิสูจน์เป็นสตริงในΣ ^* ) และผู้ตรวจสอบคือเครื่องจักรทัวริง แบบสุ่ม V ( ผู้ตรวจสอบ ) ที่ตรวจสอบการพิสูจน์πสำหรับข้อความที่ว่าxแก้ปัญหาL ได้ (หรือx ∈ L ) และตัดสินใจว่าจะยอมรับข้อความนั้นหรือไม่ ระบบนี้มีคุณสมบัติดังต่อไปนี้:

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

สำหรับความซับซ้อนในการคำนวณของตัวตรวจสอบ ตัวตรวจสอบใช้เวลาแบบพหุนาม และเรามีความซับซ้อนของการสุ่มr ( n ) เพื่อวัดจำนวนบิตสุ่มสูงสุดที่Vใช้กับx ทั้งหมด ที่มีความยาวnและความซับซ้อนของการสอบถามq ( n ) ของตัวตรวจสอบคือจำนวนการสอบถามสูงสุดที่Vทำกับ π ใช้กับx ทั้งหมด ที่ มีความยาวn

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

กล่าวกันว่าตัวตรวจสอบนั้นไม่สามารถปรับตัวได้หากมันทำการสอบถามทั้งหมดก่อนที่จะได้รับคำตอบใดๆ จากคำถามก่อนหน้า

คลาสความซับซ้อนPCP _{c ( n ), s ( n )} [ r ( n ), q ( n )]คือคลาสของปัญหาการตัดสินใจทั้งหมดที่มีระบบพิสูจน์ที่ตรวจสอบได้เชิงความน่าจะเป็นเหนือตัวอักษรไบนารีที่มีความสมบูรณ์c ( n ) และความถูกต้องs ( n ) โดยที่ตัวตรวจสอบไม่ปรับตัว ทำงานในเวลาพหุนาม และมีความซับซ้อนของความสุ่มr ( n ) และความซับซ้อนของการสอบถามq ( n )

บางครั้งมีการใช้สัญลักษณ์ย่อPCP [ r ( n ), q ( n )] แทน PCP _{1, 1/2} [ r ( n ), q ( n )]คลาสความซับซ้อนPCPถูกกำหนดเป็นPCP _{1, 1/2} [ O (log n ), O (1) ]

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

นิยามของการพิสูจน์ที่ตรวจสอบได้ด้วยความน่าจะเป็นได้รับการแนะนำอย่างชัดเจนโดย Arora และ Safra ในปี 1992 ^{[ 2 ]}แม้ว่าคุณสมบัติของมันจะได้รับการศึกษามาก่อนหน้านี้ก็ตาม ในปี 1990 Babai, Fortnow และ Lund ได้พิสูจน์ว่า PCP [ poly( n ), poly( n )] = NEXPซึ่งให้ความเท่าเทียมกันที่ไม่ธรรมดาครั้งแรกระหว่างการพิสูจน์มาตรฐาน ( NEXP ) และการพิสูจน์ที่ตรวจสอบได้ด้วยความน่าจะเป็น^{[ 3 ]}ทฤษฎีบท PCPที่พิสูจน์ในปี 1992 ระบุว่า^PCP [ O ( log n ), O (1)] = NP [ ^{2 ] [ 4 ]}

ทฤษฎีความยากของการประมาณค่าจำเป็นต้องมีความเข้าใจอย่างละเอียดเกี่ยวกับบทบาทของความสมบูรณ์ ความถูกต้อง ขนาดของตัวอักษร และความซับซ้อนของการสอบถามในบทพิสูจน์ที่ตรวจสอบได้ด้วยความน่าจะเป็น

จากมุมมองของความซับซ้อนในการคำนวณ สำหรับการตั้งค่าพารามิเตอร์แบบสุดขั้ว จะเห็นได้ว่านิยามของการพิสูจน์ที่ตรวจสอบได้เชิงความน่าจะเป็นนั้นเทียบเท่ากับคลาสความซับซ้อน มาตรฐาน ตัวอย่างเช่น เรามีสิ่งต่อไปนี้สำหรับการตั้งค่าPCP [ r ( n ), q ( n )] ที่แตกต่างกัน :

• PCP [0, 0] = P ( Pถูกกำหนดให้ไม่มีความสุ่มและไม่สามารถเข้าถึงการพิสูจน์ได้)
• PCP [ O (log n ), 0] = P (จำนวนบิตสุ่มแบบลอการิทึมไม่ได้ช่วยเครื่องทัวริงแบบเวลาพหุนาม เนื่องจากสามารถลองสตริงสุ่มที่เป็นไปได้ทั้งหมดที่มีความยาวแบบลอการิทึมได้ในเวลาพหุนาม)
• PCP [O(1), O (log n )] = P (หากไม่มีความสุ่ม การพิสูจน์สามารถคิดได้ว่าเป็นสตริงขนาดลอการิทึมคงที่ เครื่องจักรเวลาพหุนามสามารถลองพิสูจน์ขนาดลอการิทึมที่เป็นไปได้ทั้งหมดและสตริงสุ่มความยาวคงที่ได้ในเวลาพหุนาม)
• PCP [poly( n ), 0] = coRP (ตามนิยามของ coRP )
• PCP [0, poly( n )] = NP (ตามนิยามของ NP ที่อิงตามตัวตรวจสอบ )

ทฤษฎีบท PCP และMIP = NEXP สามารถอธิบายได้ดังนี้:

• PCP [ O (log n ), O (1)] = NP (ทฤษฎีบท PCP)
• PCP [poly( n ), O (1)] = PCP [poly( n ),poly( n )] = NEXP ( MIP = NEXP ) .

ตารางความเท่าเทียมกัน

⁠ ⁠${\displaystyle {\mathsf {PCP}}[r(n),q(n)]}$	0	⁠ ⁠${\displaystyle O(1)}$	⁠ ⁠${\displaystyle O(\log n)}$	⁠ ⁠${\displaystyle \operatorname {poly} (n)}$
0	พี	พี	พี	NP
⁠ ⁠${\displaystyle O(1)}$	พี	พี	พี	NP
⁠ ⁠${\displaystyle O(\log n)}$	พี	NP	NP	NP
⁠ ⁠${\displaystyle \operatorname {poly} (n)}$	คอร์พ	MIP = NEXP	เน็กซ์พี	เน็กซ์พี

เป็นที่ทราบกันดีว่าPCP [ r ( n ), q ( n )] ⊆ NTIME (poly( n ,2 ^{O ( r ( n ))} q ( n )))โดยเฉพาะอย่างยิ่งPCP [O(log n ), poly( n )] = NPในทางกลับกัน ถ้าNP ⊆ PCP [ o (log n ), o (log n )]แล้วP = NP ^{[ 2 ]}

PCP เชิงเส้น (Linear PCP) คือ PCP ที่การพิสูจน์เป็นเวกเตอร์ขององค์ประกอบในฟิลด์จำกัดและออราเคิลของ PCP ได้รับอนุญาตให้ดำเนินการเชิงเส้นกับการพิสูจน์เท่านั้น กล่าวคือ การตอบสนองจากออราเคิลต่อคำถามของผู้ตรวจสอบเป็นฟังก์ชันเชิงเส้น PCP เชิงเส้นมีการใช้งานที่สำคัญในระบบพิสูจน์ที่สามารถคอมไพล์เป็น SNARK ได้ ${\displaystyle \pi \in \mathbb {F} ^{n}}$${\displaystyle q\in \mathbb {F} ^{n}}$${\displaystyle f(q,\pi )}$

• การพิสูจน์ด้วยภาพโฮโลแกรมในสารานุกรมคณิตศาสตร์
• บันทึกการเรียนวิชา PCPโดยSubhash Khotจากมหาวิทยาลัยนิวยอร์กปี 2008
• เอกสารประกอบการเรียนวิชา PCPและประวัติความเป็นมาของทฤษฎีบท PCPโดยRyan O'DonnellและVenkatesan Guruswamiจากมหาวิทยาลัยวอชิงตันปี 2005
• สวนสัตว์แห่งความซับซ้อน : PCP