הצגת המקור של הדף "משפט PCP"

ב[[תורת הסיבוכיות]], '''משפט PCP''' (ב[[אנגלית]]: '''PCP theorem'''. האותיות PCP הן [[ראשי תיבות]] של Probabilistically Checkable Proofs - הוכחות הניתנות לבדיקה הסתברותית) קובע כי לכל [[בעיית הכרעה]] ממחלקת הסיבוכיות [[NP (מחלקת סיבוכיות)|NP]] יש הוכחות הניתנות לבדיקה הסתברותית {{אנ|probabilistically checkable proofs}} ([[הוכחה|הוכחות]] שניתן לבדוק על ידי [[אלגוריתם אקראי]]) בעלת [[סיבוכיות עץ החלטה|סיבוכיות בדיקה]] קבועה וסיבוכיות אקראיות לוגריתמית.

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

משפט PCP הוא אחת מאבני היסוד של התאוריה לחקר הקושי של הקירוב {{אנ|Hardness of approximation}}, אשר חוקרת את הקושי הטמון בעיצוב יעיל [[אלגוריתם קירוב|אלגוריתמי קירוב]] שונים לבעיות אופטימיזציה. במסגרת המחקר על הקשר של [[אלגוריתם|אלגוריתמים]] אלה למשפט PCP זכתה ב-2001 קבוצת מתמטיקאים ב[[פרס גדל]], וביניהם שני הישראלים [[שמואל ספרא]] ו[[אוריאל פייגה]].{{הערה|{{קישור כללי|כתובת=http://eatcs.org/index.php/component/content/article/507|הכותב=Efi Chita|כותרת=Gödel Prize - 2001|אתר=EATCS|שפה=אנגלית|תאריך_וידוא=2018-12-18}}}} המשפט תואר על ידי [[עודד גולדרייך]] כ"שיאו של רצף מרשים של עבודות [...] עשיר ברעיונות חדשניים".{{הערה|שם=Goldreich2008|{{Cite book|url=https://books.google.com/books?id=EuguvA-w5OEC&pg=PA405|title=Computational Complexity: A Conceptual Perspective|last=Oded Goldreich|publisher=Cambridge University Press|year=2008|isbn=978-0-521-88473-0|page=405}}}} בשנת 2019 זכתה [[אירית דינור]] בפרס גדל על הוכחה חדשה למשפט.

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

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

# ''סיבוכיות האקראיות'' <math>r(n)</math> המודדת את המספר המקסימלי של ביטים רנדומליים שהמוודא משתמש בהם כדי לאמת X כלשהו באורך n
# ''סיבוכיות הבדיקה'' <math>q(n)</math>המודדת את מספר הבדיקות שהמוודא עושה להוכחה ''π'' על X כלשהו באורך n.

בהסתמך על הגדרות אלה נגדיר את [[מחלקת סיבוכיות|מחלקת הסיבוכיות]] <math>PCP_{c(n), s(n)}[r(n), q(n)]</math> בתור המחלקה של כל בעיות ההכרעה שיש להן הוכחות הניתנות לבדיקה הסתברותית עם [[שלמות]] <math>c(n)</math> ו[[נאותות]] <math>s(n)</math>, כאשר המוודא הוא לא אדפטיבי (עושה את כל הבדיקות לפני שהוא מקבל את התשובה לגבי כל בדיקה), רץ ב[[סיבוכיות זמן|זמן פולינומלי]], ובעל ''סיבוכיות האקראיות'' <math>r(n)</math> ו''סיבוכיות הבדיקה'' <math>q(n)</math>.

כסימן מוסכם נקבע כי <math>PCP[r(n), q(n)]</math>הוא קיצור לכתיבה <math>PCP_{1,1/2}[r(n), q(n)]</math>

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

== אנלוגיה קוונטית למשפט PCP ==
בשנת [[2012]], תומאס וידיק וטויושי איטו פרסמו עבודה{{הערה|{{צ-ספר|מחבר=Oded Goldreich|שם=Computational Complexity: A Conceptual Perspective|מו"ל=Cambridge University Press|שנת הוצאה=2008-04-28|קישור=https://books.google.co.il/books?id=EuguvA-w5OEC&pg=PA405&redir_esc=y#v=onepage&q&f=false|שפה=אנגלית}}}} המראה כי ישנה מגבלה משמעותית ליכולת של מוכיחים [[שזירה קוונטית|שזורים]] לשתף פעולה במשחק מרובה משתתפים. צעד זה נחשב לצעד מרכזי ביצירת האנלוגיה הקוונטית למשפט PCP.{{הערה|שם=eurekalert_2012-July_30|
{{Cite web|url=http://www.eurekalert.org/pub_releases/2012-07/miot-mnr073012.php|title=MIT News Release: 10-year-old problem in theoretical computer science falls|date=2012-07-30|accessdate=2012-08-10|publisher=MIT News Office|last=Hardesty|first=Larry|archiveurl=https://www.webcitation.org/69otwVfyT|archivedate=2012-08-10|quote=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|
{{Cite web|url=http://web.mit.edu/newsoffice/2012/interactive-proofs-work-even-if-quantum-information-is-used-0731.html|title=10-year-old problem in theoretical computer science falls|date=2012-07-31|accessdate=2012-08-10|publisher=MIT News Office|last=Hardesty|first=Larry|archiveurl=https://www.webcitation.org/69okB9df5|archivedate=2012-08-10|quote=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.”}}
}}

== לקריאה נוספת ==
* {{לא מדויק|2009/09/19/pcp_theorem_intro|משפט ה-PCP או: איך למדתי להפסיק לדאוג ולאהוב הוכחות הניתנות לבדיקה הסתברותית}}
* [https://courses.cs.washington.edu/courses/cse533/05au/pcp-theorem.pdf הוכחת משפט PCP] - מסמך מסכם של ההוכחה של המשפט כחלק מסדרת הרצאות מ[[אוניברסיטת וושינגטון]]. {{אנגלית}}

== הערות שוליים ==
{{הערות שוליים|יישור=שמאל}}

[[קטגוריה:משפטים במדעי המחשב]]