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

בפוסט הקודם שעסק בהוכחה ש-$latex \mbox{IP}=\mbox{PSPACE}$ הראיתי מערכת הוכחה אינטראקטיבית עבור השפה $latex \overline{3\mbox{SAT}}$. זו הייתה הדוגמה הראשונה למערכת הוכחה "רצינית", כזו שמשתמשת בכל הכוח של האינטראקטיביות; במערכות האחרות שהראיתי תוך סיבוב או שניים המשחק נגמר, ואילו כאן ההוכחה הייתה דיאלוג ארוך ומתמשך, שבו לאט לאט המוכיח והמוודא התקרבו אל עצם העניין. הרעיון, כזכור, היה כזה: בהינתן פסוק לוגי $latex \varphi$, אפשר היה לתרגם אותו לפולינום $latex P_{\varphi}\left(X_{1},\dots,X_{n}\right)$ ב-$latex n$ משתנים ואת שאלת הספיקות של $latex \varphi$ לתרגם לשאלה האם $latex \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$ עבור $latex K$ כלשהו. בפולינום הזה טיפלנו על ידי כך שהצלחנו לצמצם את הבדיקה של המשוואה לעיל לבדיקה של משוואה מהצורה $latex \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}$ – כלומר, צמצנו את הבעיה באופן רקורסיבי לבעיה קטנה יותר (עם משתנה אחת פחות בפולינום החדש) מאותו הסוג. הרעיונות הללו הם בדיוק הרעיונות שנשתמש בהם גם בהוכחה ש-$latex \mbox{IP=PSPACE}$, שהיא פשוט הוכחה לכך שהשפה $latex \mbox{TQBF}$ שייכת ל-$latex \mbox{IP}$.

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

למרבה המזל, טריק פשוט יחסית פותר את הבעיה הזו. כל מה שאנחנו רוצים לדעת בהינתן פסוק $latex \mbox{TQBF}$ הוא אם ערך האמת שלו הוא $latex \mbox{T}$ או $latex \mbox{F}$. אז בואו נשים לב שערך האמת של $latex \exists x_{1}\forall x_{2}\exists x_{3}\dots\forall x_{n}\varphi\left(x_{1},\dots,x_{n}\right)$ הוא $latex \mbox{T}$ אם ורק אם $latex \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$. נסו להוכיח את זה לעצמכם – ההוכחה היא באינדוקציה פשוטה על מספר הכמתים, ומתבססת על כך ש-$latex P_{\varphi}$ מקבל או 0 או 1, ושמכפלה של שני ערכים שהוא מקבל היא 1 רק אם שניהם היו 1, ושסכום של שני ערכים שהוא מקבל הוא 0 רק אם שניהם היו 0.

אז איך הפרוטקול של הפוסט הקודם יעבוד כאן? פשוט מאוד: המוכיח ישלח למוודא פולינום במשתנה יחיד $latex g\left(X_{1}\right)$ שבתיאוריה מוגדר באמצעות הנוסחה $latex 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)$, והמוודא יוודא ש-$latex g\left(0\right)+g\left(1\right)\ne0$; וכעת המוודא ירצה להשתכנע ש-$latex g\left(X_{1}\right)$ אכן הוגדר על פי הנוסחה הנ"ל ושהמוכיח לא סתם שלח לו פולינום מונפץ, אז הוא יגריל ערך $latex a$ כלשהו מהשדה שמעליו עובדים (שהוא כזכור $latex \mathbb{Z}_{p}$ עבור $latex p$ ראשוני גדול מספיק), יחשב את $latex K=g\left(a\right)$ ויתבע מהמוכיח שיוכיח לו כעת ש-$latex \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$, והמשחק יימשך. בסיבוב הבא, המוודא יבדוק שהפולינום $latex g\left(X_{2}\right)$ שהוא קיבל מקיים דווקא $latex g\left(0\right)\cdot g\left(1\right)=K$, אבל זה לא הבדל עקרוני.

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

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

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

כעת, בפרוטוקול שהראינו בפוסט הקודם, שבו $latex g\left(X_{1}\right)$ הוגדר בתור $latex \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)$, מה שקרה הוא ש-$latex g\left(X_{1}\right)$ היה פולינום שהתקבל מחיבור הרבה פולינומים במשתנה יחיד שדרגתם לכל היותר $latex 3m$ (כי דרגת $latex P_{\varphi}$ הייתה $latex 3m$). חיבור פולינומים לא יכול להגדיל את הדרגה שלהם, ולכן $latex 3m$ נותר חסם גם על דרגת $latex g\left(X_{1}\right)$, מה שאומר שכמות המקדמים שהמוכיח צריך לשלוח למוודא כדי לשדר אליו את $latex g\left(X_{1}\right)$ הייתה סבירה ביחס לגודל הקלט של הפרוטוקול, והכל עבד יופי טופי.

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

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

בואו נעבור לתאר את העסק בצורה פורמלית, וכזו שלוכדת בו זמנית הן את פעולת הלינאריזציה והן את האופן שבו "מחסלים" כמתים – בעזרת אופרטורים. "אופרטור" כאן זה שם מפוצץ לפונקציה שלוקחת פולינום אחד ומחזירה פולינום אחר, במקרה שלנו אחד פשוט יותר. בשביל פעולת הלינאריזציה נגדיר אופרטור $latex L_{X_{i}}$ – "לינאריזציה על פי המשתנה $latex X_{i}$", שפועל כך:

$latex 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)$

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

$latex 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}$

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

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

$latex \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)$

$latex \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)$

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

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

$latex \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$

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

הפרוטוקול כעת "מקלף" את הכמתים משמאל לימין באותה שיטה של הפוסט הקודם. למשל, שימו לב לכך ש-$latex 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)$ הוא פולינום במשתנה יחיד, $latex X_{1}$, ושבגלל אופרטור הלינאריזציה בקצה השמאלי, זה פולינום ממעלה נמוכה (מעלה 1, למעשה!) ולכן המוכיח בוודאי יכול לשלוח למוודא פולינום $latex g\left(X_{1}\right)$ שלכאורה אמור להיות שווה אליו. המוודא יבדוק ש-$latex g\left(0\right)+g\left(1\right)=K$, ואז יציב אתגר חדש למוכיח, שמטרתו להוכיח ש-$latex g\left(X_{1}\right)$ הוא מה שהוא מתיימר להיות: הוא יגריל $latex a_{1}$ כלשהו מהשדה, יחשב את $latex K^{\prime}=g\left(a_{1}\right)$, ויבקש מהמוכיח להוכיח לו ש-$latex 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}$ (חשבו על זה כעל הפולינום $latex 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)$, שהוא פולינום במשתנה היחיד $latex X_{1}$, שאחר כך מציבים בו גם $latex a_{1}$).

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

בואו נתאר את התהליך באופן כללי. בכל שלב של האלגוריתם יש למוודא פולינום כלשהו, $latex h\left(X_{1},\dots,X_{n}\right)$ (שהוא $latex P\left(X_{1},\dots,X_{n}\right)$ אחרי שהופעלו עליו חלק מהאופרטורים, מימין לשמאל) ותפקידו של המוודא בחיים הוא לבדוק ש-$latex h\left(a_{1},\dots,a_{n}\right)=K$ עבור $latex K$ קבוע וערכים $latex a_{1},\dots,a_{n}$ מסויימים. שימו לב שהשימוש שלי בסימונים עשוי להיות מבלבל למדי כאן – למשל, בסיבוב הראשון של הפרוטוקול $latex h$ הוא פשוט $latex \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)$, וזה פולינום בלי משתנים חופשיים כלל. אז את הסימון $latex h\left(X_{1},\dots,X_{n}\right)$ יש לקרוא כאומר שהמשתנים שעשויים להופיע ב-$latex h$ הם $latex X_{1},\dots,X_{n}$, וש-$latex h\left(a_{1},\dots,a_{n}\right)$ הוא מה שמתקבל ב-$latex h$ כשמציבים להם את הערכים $latex a_{1},\dots,a_{n}$, כאשר משתנה שכלל לא מופיע ב-$latex h$ מן הסתם לא משפיע על התוצאה. כמו כן, לא ברור מיהם $latex a_{1},\dots,a_{n}$ בתחילת הפרוטוקול (ראינו שהם נקבעים במהלכו, ולפעמים עוברים מספר שינויים) – אז אפשר לאתחל את כולם להיות 0 או כל ערך שרירותי אחר, אבל אם אתם עדיין מצליחים לעקוב אחרי מה שהולך כאן בוודאי תראו שזה לא באמת משנה.

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

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

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

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

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

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

3 תגובות בנושא “IP=PSPACE – ההוכחה (חלק ב')”

כתיבת תגובה

האימייל לא יוצג באתר. שדות החובה מסומנים *