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

בפוסט הקודם שעסק בהוכחה ש-\( \mbox{IP}=\mbox{PSPACE} \) הראיתי מערכת הוכחה אינטראקטיבית עבור השפה \( \overline{3\mbox{SAT}} \). זו הייתה הדוגמה הראשונה למערכת הוכחה “רצינית”, כזו שמשתמשת בכל הכוח של האינטראקטיביות; במערכות האחרות שהראיתי תוך סיבוב או שניים המשחק נגמר, ואילו כאן ההוכחה הייתה דיאלוג ארוך ומתמשך, שבו לאט לאט המוכיח והמוודא התקרבו אל עצם העניין. הרעיון, כזכור, היה כזה: בהינתן פסוק לוגי \( \varphi \), אפשר היה לתרגם אותו לפולינום \( P_{\varphi}\left(X_{1},\dots,X_{n}\right) \) ב-\( n \) משתנים ואת שאלת הספיקות של \( \varphi \) לתרגם לשאלה האם \( \sum_{b_{1}\in\left\{ 0,1\right\} }\dots\sum_{b_{n}\in\left\{ 0,1\right\} }P_{\varphi}\left(b_{1},\dots,b_{n}\right)=K \) עבור \( K \) כלשהו. בפולינום הזה טיפלנו על ידי כך שהצלחנו לצמצם את הבדיקה של המשוואה לעיל לבדיקה של משוואה מהצורה \( \sum_{b_{1}\in\left\{ 0,1\right\} }\dots\sum_{b_{n-1}\in\left\{ 0,1\right\} }P^{\prime}\left(b_{1},\dots,b_{n-1}\right)=K^{\prime} \) - כלומר, צמצנו את הבעיה באופן רקורסיבי לבעיה קטנה יותר (עם משתנה אחת פחות בפולינום החדש) מאותו הסוג. הרעיונות הללו הם בדיוק הרעיונות שנשתמש בהם גם בהוכחה ש-\( \mbox{IP=PSPACE} \), שהיא פשוט הוכחה לכך שהשפה \( \mbox{TQBF} \) שייכת ל-\( \mbox{IP} \).

פסוק של \( \mbox{TQBF} \), כזכור, הוא פסוק מהצורה \( \exists x_{1}\forall x_{2}\exists x_{3}\dots\forall x_{n}\varphi\left(x_{1},\dots,x_{n}\right) \), כלומר כזה שבו מחליפים לסירוגין בין כמתי “קיים” ו”לכל”. זה הבדל משמעותי מפסוק \( \mbox{CNF} \) רגיל שבו כל הכמתים היו “קיים”. הערך \( \sum_{b_{1}\in\left\{ 0,1\right\} }\dots\sum_{b_{n}\in\left\{ 0,1\right\} }P_{\varphi}\left(b_{1},\dots,b_{n}\right) \) כבר לא ממש עוזר לנו - הוא אומר לנו מה מספר ההצבות של ערכים למשתני \( \varphi \) שיניבו \( \mbox{T} \), אבל המספר הזה לא עוזר לנו ממש - למשל, נניח ש-\( \varphi \) הוא הפסוק \( \varphi\left(x_{1},x_{2}\right)=\left(x_{1}\vee x_{2}\right)\wedge\left(\overline{x_{1}}\vee\overline{x_{2}}\right) \), שמוכר גם בסימון קצת יותר פופולרי כ-\( x_{1}\oplus x_{2} \) (פעולת XOR). לא קשה לראות כי \( \sum_{b_{1}\in\left\{ 0,1\right\} }\sum_{b_{2}\in\left\{ 0,1\right\} }\varphi\left(b_{1},b_{2}\right)=2 \), אבל \( \exists x_{1}\forall x_{2}\varphi\left(x_{1},x_{2}\right) \) הוא בבירור בעל ערך \( \mbox{F} \) (כי לא קיים \( x_{1} \) שעבורו כל \( x_{2} \) יניב ערך אמת כשמציבים את שניהם ב-\( \varphi \)). לעומת זאת, \( \varphi\left(x_{1},x_{2}\right)=x_{1} \) הוא פסוק קטן ביותר ומטופש שגם בו הסכום יהיה בדיוק 2, אבל בו התכונה כן מתקיימת (הצבה של \( \mbox{T} \) ל-\( x_{1} \) מספקת את הפסוק בלי תלות ב-\( x_{2} \), כמובן).

למרבה המזל, טריק פשוט יחסית פותר את הבעיה הזו. כל מה שאנחנו רוצים לדעת בהינתן פסוק \( \mbox{TQBF} \) הוא אם ערך האמת שלו הוא \( \mbox{T} \) או \( \mbox{F} \). אז בואו נשים לב שערך האמת של \( \exists x_{1}\forall x_{2}\exists x_{3}\dots\forall x_{n}\varphi\left(x_{1},\dots,x_{n}\right) \) הוא \( \mbox{T} \) אם ורק אם \( \sum_{b_{1}\in\left\{ 0,1\right\} }\prod_{b_{2}\in\left\{ 0,1\right\} }\sum_{b_{3}\in\left\{ 0,1\right\} }\dots\prod_{b_{n}\in\left\{ 0,1\right\} }P_{\varphi}\left(b_{1},\dots,b_{n}\right)\ne0 \). נסו להוכיח את זה לעצמכם - ההוכחה היא באינדוקציה פשוטה על מספר הכמתים, ומתבססת על כך ש-\( P_{\varphi} \) מקבל או 0 או 1, ושמכפלה של שני ערכים שהוא מקבל היא 1 רק אם שניהם היו 1, ושסכום של שני ערכים שהוא מקבל הוא 0 רק אם שניהם היו 0.

אז איך הפרוטקול של הפוסט הקודם יעבוד כאן? פשוט מאוד: המוכיח ישלח למוודא פולינום במשתנה יחיד \( g\left(X_{1}\right) \) שבתיאוריה מוגדר באמצעות הנוסחה \( g\left(X_{1}\right)=\prod_{b_{2}\in\left\{ 0,1\right\} }\sum_{b_{3}\in\left\{ 0,1\right\} }\dots\prod_{b_{n}\in\left\{ 0,1\right\} }P_{\varphi}\left(X_{1},b_{2},\dots,b_{n}\right) \), והמוודא יוודא ש-\( g\left(0\right)+g\left(1\right)\ne0 \); וכעת המוודא ירצה להשתכנע ש-\( g\left(X_{1}\right) \) אכן הוגדר על פי הנוסחה הנ”ל ושהמוכיח לא סתם שלח לו פולינום מונפץ, אז הוא יגריל ערך \( a \) כלשהו מהשדה שמעליו עובדים (שהוא כזכור \( \mathbb{Z}_{p} \) עבור \( p \) ראשוני גדול מספיק), יחשב את \( K=g\left(a\right) \) ויתבע מהמוכיח שיוכיח לו כעת ש-\( \prod_{b_{2}\in\left\{ 0,1\right\} }\sum_{b_{3}\in\left\{ 0,1\right\} }\dots\prod_{b_{n}\in\left\{ 0,1\right\} }P_{\varphi}\left(a,b_{2},\dots,b_{n}\right)=K \), והמשחק יימשך. בסיבוב הבא, המוודא יבדוק שהפולינום \( g\left(X_{2}\right) \) שהוא קיבל מקיים דווקא \( g\left(0\right)\cdot g\left(1\right)=K \), אבל זה לא הבדל עקרוני.

פוף! סיימנו. זה היה קל!

…

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

אז מה הבעיה? הבעיה היא שלא בטוח שהמוכיח יהיה מסוגל לשלוח למוודא את \( g\left(X_{1}\right) \), כי הדרגה של \( g\left(X_{1}\right) \) עשויה להיות גבוהה מדי מכדי ששליחה שלו תאפשר לפרוטוקול להמשיך להיות יעיל מבחינת זמן הריצה. בואו נעשה סדר בדברים: זמן הריצה של הבעיה נמדד ביחס לגודל הקלט, כלומר גודל הנוסחה \( \varphi \). אפשר גם כאן להניח שזו נוסחת \( 3\mbox{CNF} \) - נוסחה שמורכבת מפסוקיות כך שכל פסוקית מכילה שלושה משתנים בדיוק; נסמן ב-\( m \) את מספר הפסוקיות. את \( P_{\varphi} \) מייצגים בתור מכפלה של פולינומים שכל אחד מהם מייצג את אחת מהפסוקיות; פולינום שכזה, עם שיטת התרגום שהצגתי בפוסט הקודם, יהיה מדרגה 3, ולכן קל לייצוג (צריך לזכור את המקדמים של הפולינום, אבל יש מעט כאלו - כמה?). בסך הכל צריך כמות זכרון שהיא “בערך \( m \)” כדי לייצג את \( P_{\varphi} \), כש”בערך” פירושו “\( m \) כפול קבוע כלשהו” - מסמנים זאת \( O\left(m\right) \).

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

בפרוטוקול החדש, לעומת זאת, הכשל הוא מוחץ, שכן \( g\left(X_{1}\right) \) נבנה לא רק באמצעות חיבור פולינומים אלא גם הכפלתם; והכפלה של שני פולינומים בהחלט יכולה להגדיל את הדרגה של התוצאה: \( \left(x+1\right)\left(x-1\right)=x^{2}-1 \). מכיוון שהדרגה של פולינום התוצאה יכולה להכפיל את עצמה בכל פעם שבה אנחנו נתקלים בפעולת כפל בהגדרה של \( g\left(X_{1}\right) \), הדרגה של \( g\left(X_{1}\right) \) עשויה להיות אקספוננציאלית (ב-\( n \); שהוא בתורו עשוי בהחלט לפעמים להיות מאותו סדר גודל של \( m \)). בקיצור, רק לשלוח את כל המקדמים של \( g\left(X_{1}\right) \) מהמוכיח אל המוודא ייקח זמן רב מדי מכדי שהפרוטוקול ייחשב יעיל והכל הלך לעזאזל.

אז מה עושים? מכניסים לתמונה עוד טריק אחד, שפותר את הבעיה - לינאריזציה. לינאריזציה פירושה לקחת פולינום \( P\left(X_{1},\dots,X_{n}\right) \) כלשהו, שבו המשתנה \( X_{i} \) עשוי להופיע בדרגה גבוהה, ולהחליף אותו בפולינום חדש, \( Q\left(X_{1},\dots,X_{n}\right) \) שבו הדרגה של \( X_{i} \) היא 1 (כלומר, ב-\( Q \) לא מופיע \( X_{i}^{2} \), או \( X_{i}^{3} \) וכדומה), ועם זאת \( Q \) הוא “שקול” ל-\( P \) במובן זה שעל הצבה של ערכי 0 ו-1 למשתנים שלהם מתקבלת אותה התוצאה (וזה, כזכור, כל מה שחשוב לנו - אנחנו מנסים לברר מה מתקבל מ-\( P_{\varphi} \) כשמציבים בו 0 ו-1 בכל הצורות האפשריות ואז עושים מיש-מש מכל התוצאות).

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

\( L_{X_{i}}P\left(X_{1},\dots,X_{i},\dots,X_{n}\right)=X_{i}\cdot P\left(X_{1},\dots,1,\dots X_{n}\right)+\left(1-X_{i}\right)\cdot P\left(X_{1},\dots,0,\dots X_{n}\right) \)

כלומר, האופרטור לוקח את \( P \), מציב פעם 0 ופעם 1 במקום \( X_{i} \), מקבל שני פולינומים חדשים עם משתנה אחד פחות, כופל את האחד במשתנה \( X_{i} \) ואת השני במשתנה \( 1-X_{i} \), ומחבר. הנה דוגמה: נניח ש-\( P\left(X_{1},X_{2}\right)=X_{1}^{5}+2X_{1}^{2}X_{2}+X_{2}^{3} \). אז נקבל:

\( L_{X_{1}}P=X_{1}\left(1+2X_{2}+X_{2}^{3}\right)+\left(1-X_{1}\right)X_{2}^{3}=X_{1}+2X_{1}X_{2}+X_{2}^{3} \)

שימו לב שקיבלנו את הפולינום המקורי, רק שבכל מקום שבו הופיע \( X_{1} \) בחזקה כלשהי, עכשיו הוא מופיע בלי חזקה (או פורמלית, עם החזקה 1). זה לא מקרי, כמובן; \( P\left(X_{1},\dots,1,\dots X_{n}\right) \) הוא הפולינום \( P \) על כל מחובריו, כשהמשתנה \( X_{i} \) פשוט נמחק ממנו. לכן \( X_{i}\cdot P\left(X_{1},\dots,1,\dots X_{n}\right) \) הוא הפולינום \( P \) כאשר כל מופע קיים של \( X_{i} \) בחזקה כלשהי שונה למופע בחזקה 1; אבל לרוע המזל גם מחוברים שבהם \( X_{i} \) לא הופיע כעת כוללים אותו. זה מתוקן עם \( \left(1-X_{i}\right)P\left(X_{1},\dots,0,\dots X_{n}\right) \) - נסו להסביר לעצמכם מדוע!

כעת הבה ונגדיר אופרטורים עבור \( \forall \) ו-\( \exists \):

\( \forall_{X_{i}}P\left(X_{1},\dots,X_{n}\right)=P\left(X_{1},\dots,0,\dots,X_{n}\right)\cdot P\left(X_{1},\dots,1,\dots,X_{n}\right) \)

\( \exists_{X_{i}}P\left(X_{1},\dots,X_{n}\right)=P\left(X_{1},\dots,0,\dots,X_{n}\right)+P\left(X_{1},\dots,1,\dots,X_{n}\right) \)

כעת אפשר לנסח מחדש את הבעיה שלנו: בהינתן פולינום \( P\left(X_{1},\dots,X_{n}\right) \), נשים לב ש-\( \exists_{X_{1}}\forall_{X_{2}}\dots\exists_{X_{n}}P\left(X_{1},\dots,X_{n}\right) \) הוא פולינום קבוע, ללא משתנים, כלומר הוא ערך מספרי; האתגר של המוכיח יהיה להוכיח כי \( \exists_{X_{1}}\forall_{X_{2}}\dots\exists_{X_{n}}P\left(X_{1},\dots,X_{n}\right)=K \) עבור \( K \) נתון כלשהו.

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

\( \exists_{X_{1}}L_{X_{1}}\forall_{X_{2}}L_{X_{1}}L_{X_{2}}\dots\exists_{X_{n}}L_{X_{1}}\dots L_{X_{n}}P\left(X_{1},\dots,X_{n}\right)=K \)

יש כאן בסך הכל \( 1+2+\dots+n=O\left(n^{2}\right) \) הפעלות של אופרטור הלינאריזציה, כך שהוא לא מבזבז יותר מדי זמן ריצה.

הפרוטוקול כעת “מקלף” את הכמתים משמאל לימין באותה שיטה של הפוסט הקודם. למשל, שימו לב לכך ש-\( L_{X_{1}}\forall_{X_{2}}L_{X_{1}}L_{X_{2}}\dots\exists_{X_{n}}L_{X_{1}}\dots L_{X_{n}}P\left(X_{1},\dots,X_{n}\right) \) הוא פולינום במשתנה יחיד, \( X_{1} \), ושבגלל אופרטור הלינאריזציה בקצה השמאלי, זה פולינום ממעלה נמוכה (מעלה 1, למעשה!) ולכן המוכיח בוודאי יכול לשלוח למוודא פולינום \( g\left(X_{1}\right) \) שלכאורה אמור להיות שווה אליו. המוודא יבדוק ש-\( g\left(0\right)+g\left(1\right)=K \), ואז יציב אתגר חדש למוכיח, שמטרתו להוכיח ש-\( g\left(X_{1}\right) \) הוא מה שהוא מתיימר להיות: הוא יגריל \( a_{1} \) כלשהו מהשדה, יחשב את \( K^{\prime}=g\left(a_{1}\right) \), ויבקש מהמוכיח להוכיח לו ש-\( L_{X_{1}}\forall_{X_{2}}L_{X_{1}}L_{X_{2}}\dots\exists_{X_{n}}L_{X_{1}}\dots L_{X_{n}}P\left(a_{1},\dots,X_{n}\right)=K^{\prime} \) (חשבו על זה כעל הפולינום \( L_{X_{1}}\forall_{X_{2}}L_{X_{1}}L_{X_{2}}\dots\exists_{X_{n}}L_{X_{1}}\dots L_{X_{n}}P\left(X_{1},\dots,X_{n}\right) \), שהוא פולינום במשתנה היחיד \( X_{1} \), שאחר כך מציבים בו גם \( a_{1} \)).

מה יקרה עכשיו? המוכיח ישלח למוודא איזה \( g\left(X_{1}\right) \) שאמור להיות \( \forall_{X_{2}}L_{X_{1}}L_{X_{2}}\dots\exists_{X_{n}}L_{X_{1}}\dots L_{X_{n}}P\left(X_{1},\dots,X_{n}\right) \); המוודא יוודא ש-\( a_{1}g\left(1\right)+\left(1-a_{1}\right)g\left(0\right)=K^{\prime} \), כלומר שאם עושים ל-\( g \) לינאריזציה לפיה \( X_{1} \) ואז מציבים ב-\( X_{1} \) את הערך \( a_{1} \), אכן מקבלים את ה-\( K^{\prime} \) שאנו מצפים לקבל. כעת המוודא יבחן את המוכיח על ה-\( g \) הזה על ידי הגרלת ערך \( a \) חדש, ותביעה מהמוכיח להוכיח ש-\( g\left(a\right)=\forall_{X_{2}}L_{X_{1}}L_{X_{2}}\dots\exists_{X_{n}}L_{X_{1}}\dots L_{X_{n}}P\left(a,\dots,X_{n}\right) \) (הערך \( a_{1} \) הקודם נזרק לפח), וכן הלאה וכן הלאה. בסופו של דבר כל האופרטורים מקולפים, ולמוודא נשאר רק לוודא שמתקיים \( P\left(a_{1},a_{2},\dots,a_{n}\right)=K \) עבור ערכים \( a_{1},\dots,a_{n} \) ספציפיים, ואת זה הוא כמובן מסוגל לעשות בעצמו.

בואו נתאר את התהליך באופן כללי. בכל שלב של האלגוריתם יש למוודא פולינום כלשהו, \( h\left(X_{1},\dots,X_{n}\right) \) (שהוא \( P\left(X_{1},\dots,X_{n}\right) \) אחרי שהופעלו עליו חלק מהאופרטורים, מימין לשמאל) ותפקידו של המוודא בחיים הוא לבדוק ש-\( h\left(a_{1},\dots,a_{n}\right)=K \) עבור \( K \) קבוע וערכים \( a_{1},\dots,a_{n} \) מסויימים. שימו לב שהשימוש שלי בסימונים עשוי להיות מבלבל למדי כאן - למשל, בסיבוב הראשון של הפרוטוקול \( h \) הוא פשוט \( \exists_{X_{1}}L_{X_{1}}\forall_{X_{2}}L_{X_{1}}L_{X_{2}}\dots\exists_{X_{n}}L_{X_{1}}\dots L_{X_{n}}P\left(X_{1},\dots,X_{n}\right) \), וזה פולינום בלי משתנים חופשיים כלל. אז את הסימון \( h\left(X_{1},\dots,X_{n}\right) \) יש לקרוא כאומר שהמשתנים שעשויים להופיע ב-\( h \) הם \( X_{1},\dots,X_{n} \), וש-\( h\left(a_{1},\dots,a_{n}\right) \) הוא מה שמתקבל ב-\( h \) כשמציבים להם את הערכים \( a_{1},\dots,a_{n} \), כאשר משתנה שכלל לא מופיע ב-\( h \) מן הסתם לא משפיע על התוצאה. כמו כן, לא ברור מיהם \( a_{1},\dots,a_{n} \) בתחילת הפרוטוקול (ראינו שהם נקבעים במהלכו, ולפעמים עוברים מספר שינויים) - אז אפשר לאתחל את כולם להיות 0 או כל ערך שרירותי אחר, אבל אם אתם עדיין מצליחים לעקוב אחרי מה שהולך כאן בוודאי תראו שזה לא באמת משנה.

מה שהמוודא עושה הוא לקלף את האופרטור הבא, אם עוד קיים כזה: כלומר, לשים לב לכך ש-\( h\left(X_{1},\dots,X_{n}\right)=\Phi f\left(X_{1},\dots,X_{n}\right) \), כאשר \( \Phi \) הוא או אופרטור \( L \), או אופרטור \( \forall \), או אופרטור \( \exists \). כעת הפרוטוקול מתנהג בשלוש דרכים שונות, בהתאם לזהות האופרטור:

אם \( \Phi=\forall_{X_{i}} \) אז המוכיח שולח למוודא פולינום במשתנה יחיד \( g\left(X_{i}\right) \) שאמור להיות \( f\left(a_{1},\dots,X_{i},\dots,a_{n}\right) \). המוודא בודק ש-\( g\left(0\right)\cdot g\left(1\right)=K \). אם לא, הוא דוחה; אחרת, הוא מגריל ערך חדש של \( a_{i} \) ומבקש מהמוכיח להוכיח לו ש-\( f\left(a_{1},\dots a_{i},\dots,a_{n}\right)=g\left(a_{i}\right) \).

אם \( \Phi=\exists_{X_{i}} \) קורה אותו הסיפור כמו במקרה של \( \forall \), פרט לכך שהמוודא בודק ש-\( g\left(0\right)+g\left(1\right)=K \).

אם \( \Phi=L_{X_{i}} \) אז שוב, קורה אותו הסיפור פרט לכך שהמוודא בודק ש-\( a_{i}g\left(1\right)+\left(1-a_{i}\right)g\left(0\right)=K \).

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

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