משפט PCP

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

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

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

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

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

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

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

1. סיבוכיות האקראיות $r(n)$ המודדת את המספר המקסימלי של ביטים רנדומליים שהמוודא משתמש בהם כדי לאמת X כלשהו באורך n
2. סיבוכיות הבדיקה $q(n)$המודדת את מספר הבדיקות שהמוודא עושה להוכחה π על X כלשהו באורך n.

בהסתמך על הגדרות אלה נגדיר את מחלקת הסיבוכיות $PC{P}_{c(n),s(n)}[r(n),q(n)]$ בתור המחלקה של כל בעיות ההכרעה שיש להן הוכחות הניתנות לבדיקה הסתברותית עם שלמות $c(n)$ ונאותות $s(n)$, כאשר המוודא הוא לא אדפטיבי (עושה את כל הבדיקות לפני שהוא מקבל את התשובה לגבי כל בדיקה), רץ בזמן פולינומלי, ובעל סיבוכיות האקראיות $r(n)$ וסיבוכיות הבדיקה $q(n)$.

כסימן מוסכם נקבע כי $PCP[r(n),q(n)]$הוא קיצור לכתיבה $PC{P}_{1,1/2}[r(n),q(n)]$

משפט PCP

משפט PCP קובע כי: $NP=PCP[O(log(n)),O(1)]$. כלומר, כל בעיות ההכרעה השייכות למחלקת הסיבוכיות NP שייכות גם למחלקת הסיבוכיות PCP בהינתן סיבוכיות אקראיות לוגריתמית וסיבוכיות בדיקה קבועה.

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

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

לקריאה נוספת

• תבנית:לא מדויק
• הוכחת משפט PCP - מסמך מסכם של ההוכחה של המשפט כחלק מסדרת הרצאות מאוניברסיטת וושינגטון. תבנית:אנגלית