משפט 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 עם שלמות ונאותות (כך ש- ) מכילה שתי ישויות: "מוכיח" ו"מוודא". בהינתן פתרון משוער X באורך n, היכול להיות אמיתי או שקרי, ה"מוכיח" מייצר הוכחה π המראה כי X פותר את L. ה"מוודא" V הוא מכונת טיורינג רנדומלית עם אורקל הבודקת את ההוכחה π (המראה כי x פותר את L) ומחליטה האם לקבל הוכחה זאת.
הסיבוכיות של ה"מוודא" תוגדר בשני פרמטרים:
בהסתמך על הגדרות אלה נגדיר את מחלקת הסיבוכיות בתור המחלקה של כל בעיות ההכרעה שיש להן הוכחות הניתנות לבדיקה הסתברותית עם שלמות ונאותות , כאשר המוודא הוא לא אדפטיבי (עושה את כל הבדיקות לפני שהוא מקבל את התשובה לגבי כל בדיקה), רץ בזמן פולינומלי, ובעל סיבוכיות האקראיות וסיבוכיות הבדיקה .
כסימן מוסכם נקבע כי הוא קיצור לכתיבה
משפט PCP קובע כי: . כלומר, כל בעיות ההכרעה השייכות למחלקת הסיבוכיות NP שייכות גם למחלקת הסיבוכיות PCP בהינתן סיבוכיות אקראיות לוגריתמית וסיבוכיות בדיקה קבועה.
בשנת 2012, תומאס וידיק וטויושי איטו פרסמו עבודה[3] המראה כי ישנה מגבלה משמעותית ליכולת של מוכיחים שזורים לשתף פעולה במשחק מרובה משתתפים. צעד זה נחשב לצעד מרכזי ביצירת האנלוגיה הקוונטית למשפט PCP.[4][5]
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.