עימות המוכיחים

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

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

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

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

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

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

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

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

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

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

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

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

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

זהו!

מה הולך כאן?

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

ומה קורה אם שני הגרפים כן איזומורפיים? במקרה הזה המוכיח הוא שקרן ואנחנו רוצים שהמוודא יעיף אותו מכל המדרגות. האם זה מה שקורה?

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

אם כן, המוודא מגלה שקר בהסתברות של \( \frac{1}{2} \). זה נשמע איום ונורא, אבל זה פחות גרוע ממה שניתן לשער, מכיוון שהמוודא יכול לחזור על הפרוטוקול שוב ושוב ושוב עד אשר ישתכנע. מכיוון שכדי שיצליחו לעבוד עליו, הניחוש של המוכיח צריך להצליח בכל אחד מהסיבובים, ההסתברות שהמוודא יטעה אחרי \( n \) סיבובים היא \( \frac{1}{2^n} \) - וכבר עבור ערכים קטנים של \( n \) - למשל, 20 - ההסתברות הזו היא אפסית. נמוכה בהרבה מההסתברות שאם מרצה יגיד על שקר כלשהו “תאמינו לי”, הסטודנטים יקבלו את דבריו בלי היסוס (טוב, על מי אני עובד? ההסתברות לכך גדולה מ-50%!).

אז הכל טוב ויפה, אבל איפה נכנס אפס-הידע לעניין? על כן - בפעם הבאה.