IP=PSPACE - ההוכחה (חלק א')

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

משפט אימרמן שהצגתי לא מזמן הצטמצם בסופו של דבר לפתרון של בעיה אחת - בעיית אי-הישיגות בגרף, שהייתה מה שנקרא \( \mbox{coNL} \)-שלמה. גם הוכחה ש-\( \mbox{IP=PSPACE} \) היא בעיקרה פתרון של בעיה אחת ספציפית - \( \mbox{TQBF} \), שהוזכרה בפוסט הקודם. אם נציג מערכת הוכחה יעילה עבור בעיה זו, סיימנו, מכיוון שכל בעיה אחרת ב-\( \mbox{PSPACE} \) ניתן לתרגם לבעיית \( \mbox{TQBF} \) ולהסתפק במערכת ההוכחה עבור \( \mbox{TQBF} \) שכבר יש לנו. זה אולי ירגיז את חלקכם שרוצים לראות הוכחה שלמה ככל הניתן ל-\( \mbox{IP=PSPACE} \) ושמו לב שטרם הוכחתי ש-\( \mbox{TQBF} \) היא \( \mbox{PSPACE} \)-שלמה. זה נכון, וזה חוב שאחזיר מתישהו; אבל זה לא העיקר בהוכחה - כשנמצאה ההוכחה ל-\( \mbox{IP=PSPACE} \) הייתה עובדת היותה של \( \mbox{TQBF} \) שפה \( \mbox{PSPACE} \)-שלמה משהו ידוע ומוכר לגמרי.

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

כמו שבדרך כלל עושים עם הוכחות מסובכות, מאוד כדאי להתחיל עם הוכחה של טענה חלשה יותר, שעדיין כוללת את הרעיונות המרכזיים של הההוכחה האמיתית ובכך מקלה מאוד על העיכול שלה. במקרה שלנו, נרצה להראות מערכת הוכחה אינטראקטיבית לשפה שהיא \( \mbox{coNP} \)-שלמה - השפה \( \overline{\mbox{3SAT}} \). שפת כל פסוקי ה-CNF\( 3 \) שאינם ספיקים (פסוק CNF הוא “וגם” של הרבה פסוקיות, שכל אחת מהן היא “או” של 3 ליטרלים, שכל אחד מהם הוא משתנה או שלילה של משתנה, ופסוק הוא ספיק אם יש השמה למשתנים שנותנת לו ערך אמת). ברור שאם פסוק הוא ספיק אז קל להוכיח זאת - פשוט נותנים למוודא את ההשמה המספקת. אבל אם הוא לא ספיק לא ברור מה אפשר לעשות, ולכן מערכת הוכחה אינטראקטיבית כאן היא מעניינת. השפה 3CNF מזכירה קצת את TQBF בכך ששתיהן עוסקות בפסוקים לוגיים; ב-TQBF הפסוק עצמו גם מכיל כמתים בנוסף לכל הצרות. אבל כבר כעת ברור שאנחנו הולכים לפתור מקרה דומה יחסית.

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

איך אפשר לתרגם את משתנים לוגיים לפולינום, הרי \( \mbox{T,F} \) הם לא ערכים שבדרך כלל חוקי להציב בפולינום? ובכן, באופן טבעי יחסית נחשוב על 0 כמייצג \( \mbox{F} \) ועל 1 כמייצג \( \mbox{T} \). אם בפסוק הלוגי יש משתנה \( x_{1} \), אז בפולינום יהיה משתנה \( X_{1} \) מתאים (המעבר מאות קטנה לגדולה נועד רק כדי להבטיח שיהיה ברור מתי מדברים על פולינום ומתי מדברים על פסוק לוגי). פעולת “וגם” ניתנת לביצוע בידי כפל: \( x_{1}\wedge x_{2} \) הוא \( X_{1}\cdot X_{2} \), ובאופן כללי אם \( \varphi_{1},\varphi_{2} \) הן שתי פסוקיות שמיוצגות בידי הפולינומים \( P_{\varphi_{1}},P_{\varphi_{2}} \) אז \( \varphi_{1}\wedge\varphi_{2} \) מיוצגת על ידי \( P_{\varphi_{1}}\cdot P_{\varphi_{2}} \).

פעולת “לא” ניתנת לביצוע על ידי חיסור: \( \neg x_{1} \) מיוצג על ידי \( 1-X_{1} \), ואם \( P_{\varphi} \) מייצג את \( \varphi \) אז \( 1-P_{\varphi} \) מייצג את \( \neg\varphi \).

שתי הפעולות הללו מאפשרות ייצוג של כל פסוק שהוא כי אפשר “לסמלץ” איתן את “או” באמצעות כלל דה-מורגן: \( x_{1}\vee x_{2}=\neg\left(\neg x_{1}\wedge\neg x_{2}\right) \). במילים אחרות, את \( x_{1}\vee x_{2} \) מייצגים על ידי הפולינום \( 1-\left(1-X_{1}\right)\left(1-X_{2}\right) \).

משלושת אלו נובע שכל נוסחת 3CNF עם \( n \) משתנים, \( \varphi\left(x_{1},\dots,x_{n}\right) \), ניתן לתרגם לפולינום \( P\left(X_{1},\dots,X_{n}\right) \) ב-\( n \) משתנים. לאלו מכם שאולי מכירים רק פולינומים במשתנה אחד נציין שפולינום מרובה משתנים הוא פשוט סכום של ביטויים מהצורה \( aX_{1}^{k_{1}}X_{2}^{k_{2}}\dots X_{n}^{k_{n}} \) - כלומר, מקדם כלשהו ואז מכפלה של חזקות של המשתנים. כל ביטוי כזה נקרא מונום. הדרגה של מונום היא סכום החזקות של כל המשתנים, והדרגה של הפולינום כולו היא הדרגה הגבוהה ביותר של מונום שבו. למשל, \( 5xy+7xyz+2y^{2}z^{3} \) הוא פולינום בשלושה משתנים שדרגתו 5.

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

כעת, אם \( P_{\varphi}\left(X_{1},\dots,X_{n}\right) \) מייצג את הפסוק \( \varphi\left(x_{1},\dots,x_{n}\right) \), אז מספר ההשמות המספקות של \( \varphi \) נתון על ידי הנוסחה \( \sum_{b_{1}\in\left\{ 0,1\right\} }\sum_{b_{2}\in\left\{ 0,1\right\} }\dots\sum_{b_{n}\in\left\{ 0,1\right\} }P_{\varphi}\left(b_{1},\dots,b_{n}\right) \). זה נראה אולי קצת מפחיד במבט ראשון, אבל זה ממש לא נורא: אנחנו בסך הכל סוכמים הרבה מאוד איברים - לכל הצבה אפשרית של ערכי 0 ו-1 למשתנים \( X_{1},\dots,X_{n} \) אנחנו בודקים איזה ערך הפולינום קיבל ומוסיפים לסכום. אם כן, הפכנו את הבעיה שלנו לבעיה מסוג שונה, בעיה אלגברית יותר - בהינתן פולינום \( P\left(X_{1},\dots,X_{n}\right) \) ומספר \( K \), להוכיח ש-\( \sum_{b_{1}\in\left\{ 0,1\right\} }\dots\sum_{b_{n}\in\left\{ 0,1\right\} }P\left(b_{1},\dots,b_{n}\right)=K \). מכאן ואילך נתעסק רק בבעיה הזו.

עכשיו אתם אולי שואלים את עצמכם מה יצא לנו מכל העסק הזה - עברנו מבעיה פשוטה שמערבת פסוקים לוגיים, לבעיה יותר מסובכת עם פולינומים. הפאנץ’ המרכזי כאן הוא זה: בפולינומים אפשר להציב ערכים נוספים פרט ל-0 ו-1. הצבה שכזו נראית במבט ראשון כמו ג’יבריש, כי מה קורה כשמציבים משהו שאינו אפס או אחד בפולינום שמנסה לייצג פסוק לוגי? מקבלים תוצאה שאין לה שום משמעות שקשורה לפסוק המקורי! אבל, תזכרו שאנחנו כבר לא מנסים לפתור בעיה שקשורה לפסוקים אלא בעיה כלשהי שקשורה לפולינומים, ולכן המשמעות המקורית ההיא לא חשובה לנו יותר. כפי שנראה בקרוב, היכולת להציב בפולינום ערכים שאינם 0 או 1 היא בדיוק מה שנותן למוודא את הכוח לבחון אינטראקטיבית את המוכיח.

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

צריך להיות זהירים כאן - הטענה הזו על פולינומים נכונה רק כשהפולינום מוגדר מעל שדה, כמו המספרים הרציונליים או הממשיים. למשל, בקבוצה \( \mathbb{Z}_{16} \) של המספרים השלמים מ-0 עד 15 עם חיבור וכפל מודולו 16 לפולינום \( x^{2} \) ישנם שורשים למכביר: 0, וגם 4, וגם 8. אם כן, אפשר היה לדבר על הפולינום מעל הרציונליים, או הממשיים, אבל אלו שדות גדולים מדי לצרכים שלנו - בהמשך הפרוטוקול המוודא יצטרך לבחור באקראי איברים מהם, ומכיוון שהם שדות אינסופיים בחירה שכזו היא בעייתית. לכן עוברים לדבר על הפולינום מעל שדה סופי פשוט - קבוצה מהצורה \( \mathbb{Z}_{p} \) כאשר \( p \) הוא ראשוני (עבור ראשוניים הקבוצה הזו היא אכן שדה - הרי לכם דוגמה אחת לאופן שבו הראשוניים צצים באופן טבעי באלגברה). לכן הפרוטקול נפתח בבחירה של \( p \) גדול - כמה גדול? נדבר על זה אחר כך - על ידי המוכיח, שליחה למוודא, ובדיקה של המוודא שאותו \( p \) הוא אכן ראשוני בעזרת אלגוריתם כלשהו לבדיקת ראשוניות (מילר-רבין שהזכרתי בבלוג בעבר מספיק טוב כאן; הוא אמנם הסתברותי אבל כל מערכת ההוכחה האינטראקטיבית היא הסתברותית).

ועכשיו הטריק הוא זה: בואו נגדיר פולינום \( g\left(X\right) \) על ידי כך שניקח את הסכום של \( P \) שלעיל ונותיר בו את המשתנה הראשון בלי ידוע. כלומר:

\( g\left(X\right)=\sum_{b_{2}\in\left\{ 0,1\right\} }\dots\sum_{b_{n}\in\left\{ 0,1\right\} }P\left(X,b_{2},\dots,b_{n}\right) \) - שימו לב שהסכומים התחילו מ-\( b_{2} \). אם למוודא היה ביד את הפולינום הזה, הוא היה יכול לבדוק בקלות האם הסכום המקורי יוצא \( K \) - הוא פשוט היה מחשב את \( g\left(0\right)+g\left(1\right) \) ובודק את התוצאה (למה זה עובד?). רק מה, חישוב של \( g\left(X\right) \) הוא בעייתי כמעט כמו חישוב של כל הסכומים, אם כי הוא טיפה פחות בעייתי שכן יש משתנה אחד פחות שמעורב במשחק. אז במקום לחשב את הפולינום בעצמו, המוודא יבקש מהמוכיח לשלוח לו אותו - כלומר, לשלוח למוודא את סדרת המקדמים של הפולינום. מעלת הפולינום היא אותה מעלה כשל \( P \) שכבר הסברנו שאינה גדולה, כך שמספר המקדמים שהמוכיח שולח אינו גדול. אחרי שהמוודא קיבל מהמוכיח את \( g \) הוא יכול לחשב את \( g\left(0\right)+g\left(1\right) \), ואם קיבל משהו שונה מ-\( K \), לדחות מייד. אבל אם הוא קיבל, כצפוי, \( K \), מה עכשיו? הוא לא יכול לקבל, מהטעם הפשוט שהוא לא סומך על המוכיח! מה אם המוכיח שלח לו סתם פולינום שלא קשור ל-\( P \) בשום צורה (והינדס את הפולינום כדי שכן יקיים \( g\left(0\right)+g\left(1\right)=K \))?

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

כאן מגיע הפאנץ’ המובטח. המוודא יגריל מספר כלשהו \( a \) מתוך השדה, יציב אותו ב-\( g \) ויקבל מספר, \( g\left(a\right) \). כעת הוא יפנה למוכיח את האתגר הבא: הוכח נא עבורי שמתקיים \( \sum_{b_{2}\in\left\{ 0,1\right\} }\dots\sum_{b_{n}\in\left\{ 0,1\right\} }P\left(a,b_{2},\dots,b_{n}\right)=g\left(a\right) \). אבל מה זה האתגר הזה? זה בדיוק אותו דבר שהתחלנו ממנו - המוכיח מנסה להוכיח למוודא שאם לוקחים פולינום, מציבים במשתנים שלו את כל הקומבינציות האפשריות של 0 ו-1 וסוכמים, מקבלים מספר מסויים. ההבדל היחיד הוא שהפולינום החדש הוא בעל פחות משתנים, כי “חיסלנו” את אחד המשתנים על ידי כך שהצבנו בו \( a \).

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

הדרך היחידה שבה המוכיח יוכל לעבוד על המוודא כאן תהיה אם הוא יגריל פולינום \( g \) כך שבאורח קסום מתקיים \( \sum_{b_{2}\in\left\{ 0,1\right\} }\dots\sum_{b_{n}\in\left\{ 0,1\right\} }P\left(a,b_{2},\dots,b_{n}\right)=g\left(a\right) \) וזאת למרות ש-\( g \) איננו הפולינום שמוגדר על ידי המשוואה \( \sum_{b_{2}\in\left\{ 0,1\right\} }\dots\sum_{b_{n}\in\left\{ 0,1\right\} }P\left(X,b_{2},\dots,b_{n}\right) \). מה הסיכוי שזה יקרה?

באופן כללי אם \( p,q \) הם שני פולינומים במשתנה יחיד, מה ההסתברות ש-\( p\left(a\right)=q\left(a\right) \) עבור \( a \) שנבחר באקראי? ובכן, זו ההסתברות ש-\( a \) יהיה שורש של הפולינום \( p\left(a\right)-q\left(a\right) \) - פולינום שאינו זהותית אפס, ולכן מספר שורשיו הוא לכל היותר כדרגת פולינום ההפרש - נאמר שהיא \( d \). אז ההסתברות להצלחה היא \( \frac{d}{p} \), וכאן צריך לחשוב על \( d \) כקטן יחסית ועל \( p \) כגדול. מכאן שההסתברות שהמוכיח לא יצליח לעבוד על המוודא בסיבוב מסויים היא \( \left(1-\frac{d}{p}\right) \), ואם יש \( n \) סיבובים סך הכל בפרוטוקול, ההסתברות שהמוכיח לא יצליח לעבוד על המוודא באף אחד מהם היא \( \left(1-\frac{d}{p}\right)^{n} \), ולא קשה לראות שזה מספר גדול מספיק כדי שהפרוטוקול יהיה מוצלח.

האם סיימנו? חס ושלום, לא. הראינו ש-\( \overline{3\mbox{SAT}}\in\mbox{IP} \), אבל לא ש-\( \mbox{TQBF}\in\mbox{IP} \). הפרוטקול שראינו כולל את מרבית הרעיונות של ההוכחה הכללית, אבל יש תעלול אחד נוסף שנזדקק לו. למה ומדוע? נסו לחזור על אותה הוכחה עבור \( \mbox{TQBF} \) ובדקו היכן אתם נתקעים. נסביר את הכל בפוסט הבא בנושא.