משפט PCP

בתורת הסיבוכיות, משפט PCP (באנגלית: PCP theorem. האותיות PCP הן ראשי תיבות של Probabilistically Checkable Proofs - הוכחות הניתנות לבדיקה הסתברותית) קובע כי לכל בעיית הכרעה ממחלקת הסיבוכיות NP יש הוכחות הניתנות לבדיקה הסתברותית (אנ') (הוכחות שניתן לבדוק על ידי אלגוריתם אקראי) בעלת סיבוכיות בדיקה קבועה וסיבוכיות אקראיות לוגריתמית.

משפט PCP קובע כי לכל n קיים קבוע אוניברסלי K, כך שכל הוכחה מתמטית באורך n יכולה להיכתב מחדש כהוכחה באורך poly(n) הניתנת לאימות בדיוק של 99% באמצעות אלגוריתם אקראי הבוחן רק K מהאותיות של ההוכחה.

משפט PCP הוא אחת מאבני היסוד של התאוריה לחקר הקושי של הקירוב (אנ'), אשר חוקרת את הקושי הטמון בעיצוב יעיל אלגוריתמי קירוב שונים לבעיות אופטימיזציה. במסגרת המחקר על הקשר של אלגוריתמים אלה למשפט PCP זכתה ב-2001 קבוצת מתמטיקאים בפרס גדל, וביניהם שני הישראלים שמואל ספרא ואוריאל פייגה.^[1] המשפט תואר על ידי עודד גולדרייך כ"שיאו של רצף מרשים של עבודות [...] עשיר ברעיונות חדשניים".^[2] בשנת 2019 זכתה אירית דינור בפרס גדל על הוכחה חדשה למשפט.

הגדרה פורמלית

הגדרת הוכחות הניתנות לבדיקה הסתברותית

בהינתן בעיית הכרעה L, הוכחה הניתנת לבדיקה הסתברותית (probabilistically checkable proof system) של L עם שלמות $c(n)$ ונאותות $s(n)$ (כך ש- $1\geq c(n)\geq s(n)\geq 0$ ) מכילה שתי ישויות: "מוכיח" ו"מוודא". בהינתן פתרון משוער X באורך n, היכול להיות אמיתי או שקרי, ה"מוכיח" מייצר הוכחה π המראה כי X פותר את L. ה"מוודא" V הוא מכונת טיורינג רנדומלית עם אורקל הבודקת את ההוכחה π (המראה כי x פותר את L) ומחליטה האם לקבל הוכחה זאת.

הסיבוכיות של ה"מוודא" תוגדר בשני פרמטרים:

סיבוכיות האקראיות $r(n)$ המודדת את המספר המקסימלי של ביטים רנדומליים שהמוודא משתמש בהם כדי לאמת X כלשהו באורך n
סיבוכיות הבדיקה $q(n)$ המודדת את מספר הבדיקות שהמוודא עושה להוכחה π על 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 קובע כי: $NP=PCP[O(log(n)),O(1)]$ . כלומר, כל בעיות ההכרעה השייכות למחלקת הסיבוכיות NP שייכות גם למחלקת הסיבוכיות PCP בהינתן סיבוכיות אקראיות לוגריתמית וסיבוכיות בדיקה קבועה.

אנלוגיה קוונטית למשפט PCP

בשנת 2012, תומאס וידיק וטויושי איטו פרסמו עבודה^[3] המראה כי ישנה מגבלה משמעותית ליכולת של מוכיחים שזורים לשתף פעולה במשחק מרובה משתתפים. צעד זה נחשב לצעד מרכזי ביצירת האנלוגיה הקוונטית למשפט PCP.^[4]^[5]

לקריאה נוספת

גדי אלכסנדרוביץ', משפט ה-PCP או: איך למדתי להפסיק לדאוג ולאהוב הוכחות הניתנות לבדיקה הסתברותית, באתר "לא מדויק", 19 בספטמבר 2009
הוכחת משפט PCP - מסמך מסכם של ההוכחה של המשפט כחלק מסדרת הרצאות מאוניברסיטת וושינגטון. (באנגלית)

הערות שוליים

^ Efi Chita, Gödel Prize - 2001, EATCS (באנגלית)
^ Oded Goldreich (2008). Computational Complexity: A Conceptual Perspective. Cambridge University Press. p. 405. ISBN 978-0-521-88473-0.
^ Oded Goldreich, Computational Complexity: A Conceptual Perspective, Cambridge University Press, 2008-04-28. (באנגלית)
^ Hardesty, Larry (2012-07-30). "MIT News Release: 10-year-old problem in theoretical computer science falls". MIT News Office. אורכב מ-המקור ב-2012-08-10. נבדק ב-2012-08-10. Interactive proofs are the basis of cryptographic systems now in wide use, but for computer scientists, they're just as important for the insight they provide into the complexity of computational problems.
^ Hardesty, Larry (2012-07-31). "10-year-old problem in theoretical computer science falls". MIT News Office. אורכב מ-המקור ב-2012-08-10. נבדק ב-2012-08-10. Dorit Aharonov, a professor of computer science and engineering at Hebrew University in Jerusalem, says that Vidick and Ito’s paper is the quantum analogue of an earlier paper on multiprover interactive proofs that “basically led to the PCP theorem, and the PCP theorem is no doubt the most important result of complexity in the past 20 years.” Similarly, she says, the new paper “could be an important step toward proving the quantum analogue of the PCP theorem, which is a major open question in quantum complexity theory.”

[1] Efi Chita, Gödel Prize - 2001, EATCS (באנגלית)

[Goldreich2008-2] Oded Goldreich (2008). Computational Complexity: A Conceptual Perspective. Cambridge University Press. p. 405. ISBN 978-0-521-88473-0.

[3] Oded Goldreich, Computational Complexity: A Conceptual Perspective, Cambridge University Press, 2008-04-28. (באנגלית)

[eurekalert_2012-July_30-4] Hardesty, Larry (2012-07-30). "MIT News Release: 10-year-old problem in theoretical computer science falls". MIT News Office. אורכב מ-המקור ב-2012-08-10. נבדק ב-2012-08-10. Interactive proofs are the basis of cryptographic systems now in wide use, but for computer scientists, they're just as important for the insight they provide into the complexity of computational problems.

[MIT_newsoffice_2012_July_31-5] Hardesty, Larry (2012-07-31). "10-year-old problem in theoretical computer science falls". MIT News Office. אורכב מ-המקור ב-2012-08-10. נבדק ב-2012-08-10. Dorit Aharonov, a professor of computer science and engineering at Hebrew University in Jerusalem, says that Vidick and Ito’s paper is the quantum analogue of an earlier paper on multiprover interactive proofs that “basically led to the PCP theorem, and the PCP theorem is no doubt the most important result of complexity in the past 20 years.” Similarly, she says, the new paper “could be an important step toward proving the quantum analogue of the PCP theorem, which is a major open question in quantum complexity theory.”

[1]

[2]

[3]

[4]

[5]