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

אחד מהנושאים הלוהטים ביותר במדעי המחשב המודרניים הוא משפט ה-PCP, הרחבותיו והשלכותיו. אלא שכל הקשור ל-PCP עשוי להישמע מוזר מאוד כששומעים לראשונה מה ראשי התיבות הללו מסמלים: Probabilistically Checkable Proofs, הוכחות הניתנות לבדיקה הסתברותית. מה זה בכלל, ואיך אפשר לזהם מושג טהור כמו “הוכחה” שהיא תמיד ודאית ב-100 אחוז (לפחות כשמדובר על הוכחה “מתמטית”) עם המושג הבזוי של “הסתברות”?

לשם כך ראשית יש להציג את הגישה של מדעי המחשב למושג ההוכחה, שהוא שונה מעט מהגישה המתמטית. בגישה המתמטית אנו קובעים מערכת של אקסיומות וכללי היסק, ואז הוכחה היא פשוט סדרה של טענות כך שכל טענה היא אקסיומה או נובעת מטענות קודמות באמצעות כללי ההיסק. דיברתי בפירוט רב יותר על מערכות שכאלו כאשר הזכרתי את משפטי גדל. כמובן, אפילו במתמטיקה זו איננה המשמעות היחידה של “הוכחה” (למשל, אפשר לחשוב על מערכות שבהן מוכיחים דברים בדרך השלילה - מתחילים מטענה כלשהי ומסיקים לבסוף סתירה. אלו מערכות הוכחה מעניינות בפני עצמן), אבל זו המשמעות המקובלת ביותר.

במדעי המחשב נוקטים גישה אחרת, שבמובן מסויים היא “טבעית” יותר. הבה ונחשוב לרגע על ספר מתמטיקה. ההוכחות שנמצאות בו למשפטים אינן, על פי רוב, הוכחות במובן המתמטי הפורמלי; כמעט כל הוכחה בספרים נכתבת בשפה טבעית, מסבירה דברים ב”נפנוף ידיים”, משאירה חלק מההוכחה כתרגיל לקורא, מבצעת מעברים מורכבים בלי שום נימוק של סדרת הצעדים שבאמצע (שלעתים נדרש קורס שלם כדי להכיר אותם) וכן הלאה. עם זאת, על פי רוב ההוכחות הלו נחשבות ללגיטימיות ואפילו להכרחיות, שכן כל נסיון לכתוב הוכחה פורמלית יגרום להוכחה להיות ארוכה בהרבה וקריאה הרבה פחות על ידי בני אדם.

אם כן, הדגש המרכזי כאן הוא על היעילות שבה ההוכחה מסוגלת להיקרא בידי מי שקורא אותה. בפרט, אנחנו מתייחסים אל הקורא כאל חלק אינטגרלי ממערכת ההוכחה - לקוראים שונים אולי יתאימו הוכחות שונות. לכן הגדרת ההוכחה מפסיקה לדבר על איזה שהוא ערך פנימי שטמון בה, והיא הופכת להיות תלויה לחלוטין בהשפעה שלה על הקורא. מה שעוד נותר לדבר עליו הוא מהם הדברים שההוכחה מנסה להוכיח, וגם כאן נכנסת לתמונה הגישה של מדעי המחשב.

במקום לדבר על הוכחה של טענה בשפה מסדר ראשון או כל דבר דומה, מפשיטים; טענה, בשורה התחתונה, היא רצף של אותיות מעל אלפבית כלשהו, שהוא או נכון או לא נכון תחת פירוש מסויים שאנחנו נותנים לעולם. יותר במובהק, אם אנחנו קובעים את האלפבית שלנו מראש ואת הפרשנות שלנו לעולם מראש, אנחנו נשארים עם שלושה סוגים שונים של רצפי אותיות - כאלו שאין להם שום משמעות (למשל “עגכדהא”), כאלו שיש להם משמעות והם נכונים (“יש אינסוף מספרים ראשונים”) וכאלו שיש להם משמעות והם אינם נכונים (“יש מספר סופי של ראשוניים”). על כל טענה כזו אפשר לחשוב בתור “מילה” - רצף אותיות (במקרה שלנו, כולל האות “רווח”), ועל אוסף הטענות הנכונות אפשר לחשוב בתור שפה (שפה היא פשוט אוסף של מילים). כלומר, צמצמנו את הבעיה שלנו לבעיה של זיהוי מתי מילה שייכת לשפה כלשהי. זה גם בדיוק המושג שהופיע בפוסטים הקודמים שלי, שעסקו באוטומטים; מה שחשוב להבין הוא שדרך ההתבוננות הזו לא גורעת מהכלליות של הדיון על הוכחה אלא רק מרחיבה אותו.

בואו נחשוב על כמה דוגמה פשוטה, להבדיל מכל מערכות ההוכחה מסדר ראשון ודומיהן. אפשר לחשוב על שפה של גרפים שיש בהם מסלול המילטוני (מסלול שמבקר בכל הצמתים בדיוק פעם אחת). בהקשר הזה אנחנו מפרשים כל מילה בתור גרף (או אומרים “המילה הזו מקושקשת ואי אפשר לחשוב עליה כאילו היא מתארת גרף”), והשפה שלנו תכלול בדיוק את אותן מילים שמייצגות גרפים המילטוניים. במקרה הזה טענה מסוג “המילה הזו שייכת לשפה” היא בעצם טענת “הגרף הזה הוא המילטוני”.

עכשיו, בהינתן גרף המילטוני, איך אפשר להשתכנע בכך שהוא אכן המילטוני? הבה ונקרא למי שמנסה להשתכנע “המוודא” (כי הוא מוודא שהטענה נכונה). המוודא יכול לנסות באופן שרירותי את כל המסלולים בגרף עד שימצא אחד המילטוני (או שלא ימצא, ואז ידע בודאות שהגרף אינו המילטוני). עם זאת, אפשר לעשות לו את החיים קלים יותר ולספק לו מראש תיאור של מסלול המילטוני בגרף - ואז כל מה שיישאר לו לעשות הוא לוודא שאכן התיאור הזה חוקי ומתאים לגרף. אם מישהו רמאי ייתן לו תיאור שקרי, המוודא יעלה על זה בקלות. זה מביא אותנו סוף סוף אל ההגדרה הפורמלית של “מערכת הוכחה עבור השפה \( L \)”: היא מורכבת ממוודא \( V \), שאפשר לחשוב עליו בתור אלגוריתם מתוחכם (אבל עדיין אלגוריתם - כזה שכל צעד שלו מוגדר בצורה מדוייקת) שמקבל שני “קלטים” - טענה \( w \), והוכחה \( \pi \). הן הטענה והן ההוכחה הן פשוט מילים; המוודא רץ על שני הקלטים הללו ופולט לבסוף “מקבל” או “דוחה”. פורמלית ניתן לכתוב זאת \( V\left(w,\pi\right)=\mbox{acc} \) ו-\( V\left(w,\pi\right)=\mbox{rej} \). הציפיות שלנו ממערכת הוכחה “טובה” (כלומר, ממוודא “טוב”) הן שיתקיימו שלוש הדרישות הבאות:

1. שלמות: לכל \( w\in L \) קיימת הוכחה \( \pi \) כך ש-\( V\left(w,\pi\right)=\mbox{acc} \).
2. נאותות: לכל \( w\notin L \) ולכל הוכחה \( \pi \) מתקיים \( V\left(w,\pi\right)=\mbox{rej} \).
3. יעילות: צריכת המשאבים של \( V \) על הקלטים \( w,\pi \) היא יעילה ביחס לגודל הייצוג של \( w \).

שתי הדרישות הראשונות הן מתמטיות “קלאסיות”, בזמן שהשלישית היא מדעי-המחשבניקית “מודרנית”. זו גם הדרישה הכי מעורפלת, ולכן אתמקד מעכשיו בפורמליזציה הסטנדרטית שלה- אנו דורשים כי זמן הריצה של \( V \) יהיה פולינומי בגודל \( w \). פולינומי, שכן זה מה שנחשב לזמן ריצה סביר בדרך כלל. כעת נשאלת השאלה מהן השפות שמקיימות את שלוש התכונות הללו. התשובה היא שאלו הן בדיוק השפות שבמחלקה המפורסמת \( \mbox{NP} \) שהזכרתי כאן לא אחת. אין כאן שום תובנה מחוכמת - ה”הוכחה” שמקבל \( V \) היא אותו דבר במהותו כמו ה”רמז” שבדרך כלל נהוג לומר שהמכונה לשפת ה-\( \mbox{NP} \) מקבלת (אם חושבים על \( \mbox{NP} \) כעל אוסף השפות שיש מכונה אי דטרמיניסטית שמכריעה אותן השקילות מעט פחות ברורה - ה”הוכחה” במקרה זה תהיה תיאור של הבחירות האי דטרמיניסטיות שהמכונה מבצעת עד לקבלת המילה השייכת לשפה).אם כן, במובן מסויים \( \mbox{NP} \) מסמלת עבורנו את מחלקת כל ה”תורות” שקיימת עבורן מערכת הוכחה יעילה. לאן ממשיכים מכאן?

כיוון אחד שניתן להמשיך אליו הוא הרחבה של מושג ה”הוכחה”. במקום סתם הוכחה כתובה \( \pi \), אפשר לדבר על “מוכיח” \( P \) שמנהל שיחה מנומסת עם \( V \) ומנסה לשכנע אותו שהוא צודק. למערכת הוכחה כזו קוראים “מערכת הוכחה אינטראקטיבית”. לרוע המזל, ניתן להוכיח כי השינוי הזה לא מוסיף כוח למערכת - גם מערכת הוכחה אינטראקטיבית מסוגלת להוכיח רק שפות ב-\( \mbox{NP} \). אם כן, צריך להקל איכשהו על אחת משלוש הדרישות שלנו. על יעילות לא רוצים לוותר בשום פנים ואופן, ולכן נותרו השלמות והנאותות. אם נלך לפי הגישה לפיה עדיפים עשרה פושעים מחוץ לכלא מאשר איש חף מפשע אחד בתוכו, הרי שעלינו לפגוע בנאותות, לא בשלמות; פגיעה בשלמות פירושה שייתכן שטענות נכונות לא יהיו ניתנות להוכחה; פגיעה בנאותות פירושה שיהיה אפשרי להשתכנע בטעות שטענה שגויה היא נכונה. החוכמה היא להגביל את ה”אפשרי” הזה ככל הניתן.

לא מזמן דיברתי על אלגוריתמים הסתברותיים. הדגשתי שם שהדבר החשוב באלגוריתם הסתברותי הוא שההסתברות תילקח על פני כל הריצות האפשריות של האלגוריתם על קלט מסויים, ולא על פני כל הקלטים. ההבדל מהותי: במקום שיהיו קלטים שעבורם האלגוריתם תמיד נכשל אבל “ההסתברות שהם יתקבלו” היא נמוכה (במרכאות, כי זה מושג מאוד בעייתי), האלגוריתם מבטיח הסתברות הצלחה כלשהי לכל הקלטים. כך גם במערכת הוכחה - אנחנו דורשים שלכל מילה \( w\notin L \) ולכל “הוכחה” \( \pi \) עבור \( w \) (“הוכחה” כזו היא בעצם נסיון להטעות את המוודא), ההסתברות שיתקיים \( V\left(w,\pi\right)=\mbox{rej} \) היא לפחות \( \frac{2}{3} \) או קבוע דומה (בפוסט על אלגוריתמים הסתברותיים הסברתי מדוע בחירת הקבוע אינה כה מהותית). כמובן שזה אומר, בפרט, שהמוודא פועל באופן הסתברותי.

אם מקבלים את ההקלה הזו של תנאי 2, פתאום מערכות ההוכחה שלנו מקבלות כוח רב הרבה יותר. אם הולכים בכיוון של מערכות הוכחה אינטראקטיביות, הרי שמתברר כי מערכת הוכחה אינטראקטיבית עם ההקלה ההסתברותית שהצגנו הופכת להיות חזקה כמו \( \mbox{PSPACE} \): כל בעיה שניתנת לפתרון בזכרון פולינומי, ניתנת להוכחה במערכת כזו. השלב הבא, והמשעשע עוד יותר, הוא הרחבת המערכת האינטראקטיבית כך שיהיו שני מוכיחים במקום אחד, כך שהמוודא מדבר עם כל אחד מהמוכיחים בנפרד, מבלי שהם יוכלו לתקשר זה עם זה. הדבר מזכיר קצת שני פושעים שנחקרים בנפרד והשקרים שהם מספרים אינם מתואמים, כך שקל לעלות עליהם. במדעי המחשב התחושה האינטואיטיבית הזו תורגמה לתוצאה מדוייקת - מערכות הוכחה שכאלו תופסות את כל \( \mbox{NEXP} \) - אוסף הבעיות שניתנות לפתרון אי דטרמיניסטי בזמן אקספוננציאלי. מחלקה זו גדולה לפחות כמו \( \mbox{PSPACE} \) (ככל שידוע לי, השאלה האם הן שוות או לא עודנה פתוחה).

עם זאת, הכיוון שאני רוצה לדבר עליו כעת אינו הכיוון האינטראקטיבי - נמשיך לדבר על הסיטואציה שבה המוודא מקבל הוכחה כתובה ותו לא. מכיוון שההסתברות מוסיפה לו כוח רב, מעניין לשאול איך אפשר “להצטמצם” כעת באופן אחר ועדיין לתפוס את מה שתפסה ההגדרה ה”קלאסית” להוכחה, כלומר את \( \mbox{NP} \). זה בדיוק המקום שבו נכנס משפט ה-\( \mbox{PCP} \) לתמונה.

כל בודק תרגילים (לפחות בתחום הריאלי) ודאי מכיר את התופעה הזו - אחרי שבודקים ארבע-חמש עבודות, כבר נהיה ברור לחלוטין מה דרך הפתרון שבה רוב הפותרים נוקטים ואיפה נמצאים ה”מוקשים” שבהם הם נכשלים. מאותו רגע, בדיקת העבודות מתקצרת - במקום לנבור בכל הטקסט, די לאתר ולבדוק את ה”מוקשים” וחסל. זו לא דרך מדוייקת לחלוטין, ולכן לפעמים נוצר אילוץ לקרוא את העבודה כולה, אבל בדרך כלל די בבדיקת המוקשים ורפרוף מהיר על יתר הפתרון. כלומר, ההוכחה ניתנת לבדיקה מבלי שנקרא את כולה.

זה גם בדיוק הרעיון שמנחה את ה-PCP: להגביל את כמות המידע שניתן לקרוא מתוך ההוכחה עצמה. זה גם מעלה את השאלה, שעד כה די הסתרתי, מה צריך להיות אורכה של ההוכחה. עד כה לא דרשתי שום דרישה על אורך ההוכחה, אבל כן דרשתי שהמוודא ירוץ בזמן פולינומי באורך \( w \); מכיוון שעד כה המוודא היה דטרמיניסטי, נבע מכך שגם מההוכחה עצמה הוא יוכל לקרוא מספר תווים שהוא לכל היותר פולינומי ב-\( w \), ולכן לא היה טעם לדבר על הוכחות ארוכות יותר; דה-פקטו, ההוכחת היו מאורך פולינומי ב-\( w \). לרוב בדיונים על \( \mbox{NP} \) הדרישה הזו מבוצעת במפורש.

אלא שכעת איננו חייבים לקרוא את כל ההוכחה - אנחנו יכולים לדגום תווים ממנה באקראי. למשל, להגריל את תו 13, תו 57 ותו 42,423 ולהחליט שרק אותם נקרא. גם כאן יש עניינים טכניים כלשהם של “איך קוראים את התו במקום ה-1,000,000,000 במהירות?” שלא אכנס אליהם (מה שעושים בפועל הוא להניח שההוכחה נתונה כ”קופסה שחורה” - בהינתן קלט של מקום בהוכחה, הקופסה מחזירה את התו שנמצא באותו מקום). מכאן שאנו מאפשרים להוכחות להיות ארוכות מאוד, אבל מרשים קריאה רק של חלק מצומצם מהן.

הדבר הנוסף שאותו ניתן להגביל הוא כמות האקראיות שבה מותר למוודא להשתמש (מספר ה”מטבעות” שיהיה מותר לו להטיל). שימו לב לקשר עדין ולא ברור מיידית בין נתון זה ובין גודל ההוכחה - אם לא ניתן להגריל יותר מדי ביטים, גם לא ניתן להגריל אינדקסים יותר מדי גדולים של מקומות בהוכחה; לכן מגבלה על מספר הביטים האקראיים שזמינים לנו כופה מגבלה דה-פקטו על הגודל האפקטיבי של ההוכחה.

וכעת מגיע הפאנץ’. נסמן ב-\( \mbox{PCP}\left(r\left(n\right),q\left(n\right)\right) \) את אוסף הבעיות שקיימת עבורן מערכת הוכחה מהסוג שתיארתי, שבה על קלט מאורך \( n \) ניתן להשתמש לכל היותר ב-\( O\left(r\left(n\right)\right) \) ביטים של אקראיות ולקרוא לכל היותר \( O\left(q\left(n\right)\right) \) ביטים מההוכחה. כך למשל \( \mbox{NP}=\mbox{PCP}\left(0,\mbox{poly}\left(n\right)\right) \) מתקיים בבירור (\( \mbox{poly} \) פירושו שאנו מרשים ל-\( q\left(n\right) \) להיות פולינום מכל חזקה שהיא; בפועל פירוש הדבר הוא גישה חופשית להוכחה כולה כל עוד עומדים במגבלות הזמן). התוצאה המפתיעה של משפט ה-\( \mbox{PCP} \) היא שמתקיים גם \( \mbox{NP}=\mbox{PCP}(\log(n),1) \).

במילים - אם מרשים שימוש ב-\( O\left(\log n\right) \) ביטים של אקראיות (וזה לא הרבה בכלל), אפשר להסתפק בקריאה של מספר קבוע של ביטים מההוכחה. קבוע, כלומר לא תלוי בכלל באורך \( w \). פירוש הדבר הוא, לדוגמה, שבבעיית המעגל ההמילטוני מספיק תמיד לקרוא 13 ביטים (שנבחרים באקראי) מההוכחה ואז לבצע כמה חישובים, ואין זה משנה כלל אם הגרף הנבדק הוא בעל 10 צמתים או בעל \( 10^{100} \) צמתים. לטעמי האישי זוהי תוצאה מדהימה.

כמובן, יש דברים שמסתתרים כאן מאחורי הקלעים; בפרט, יש מספר גרסאות שונות למשפט (כולן אומרות כי \( \mbox{NP}=\mbox{PCP}\left(\log\left(n\right),1\right) \) אך נבדלות בקבועים ובפרמטרים נוספים שמאחורי הקלעים - למשל, דרישות השלמות והנאותות נפגעות בצורות שונות ומשונות). בגרסה שאני מתמקד בה, גודלה של ההוכחה יהיה עצום (אך כאמור, לא נצטרך לקרוא את כולה). בפוסטים הבאים אתאר (בעיקר בנפנופי ידיים, כי מדובר בנושא טכני למדי) את ההוכחה של גרסה מוחלשת של המשפט בכדי לתת תחושה של “מה הולך כאן בכלל”, ולהציג את הנושא היפהפה בזכות עצמו שעליו ההוכחה מסתמכת - קודים לתיקון שגיאות. לעת עתה, אני מקווה שהתוצאה מצליחה להיות מעניינת בזכות עצמה.