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

באופן טבעי אנחנו מפנים את מבטנו אל המחלקה \(\mbox{coNP}\), של הבעיות ה"משלימות" לבעיות ב-\(\mbox{NP}\). אם ב-\(\mbox{NP}\) יש את השפה "הגרפים שניתנים לצביעה ב-3 צבעים", הרי שב-\(\mbox{coNP}\) יש את השפה "הגרפים שאינם ניתנים לצביעה ב-3 צבעים". רק מה? רוב הבעיות שאנו מכירים ב-\(\mbox{coNP}\) הן או קלות (כלומר, ב-\(\mbox{P}\)) או ממש קשות – מה שנקרא "\(\mbox{coNP}\)-שלמות". פירוש הדבר הוא שאם פתרנו בעיה אחת מהן, פתרנו את כל \(\mbox{coNP}\). עבורנו זה אומר שאם נמצא מערכת הוכחה אינטראקטיבית עבור בעיה כלשהי שהיא \(\mbox{coNP}\) שלמה, הדבר נותן לנו מערכת הוכחה אינטראקטיבית עבור כל שפה ב-\(\mbox{coNP}\). אני באמת הולך להראות מערכת הוכחה שכזו, כחלק מההוכחה ש-\(\mbox{IP=PSPACE}\); אבל זו כבר מערכת מסובכת למדי. האם קיימות מערכות פשוטות עבור שפות שהן \(\mbox{coNP}\)-שלמות? זו שאלה טובה והתשובה עליה כנראה שלילית אם אנחנו מזהים "פשטות" עם "מספר סיבובים קבוע". קיימת הוכחה שאם יש מערכת הוכחה אינטראקטיבית בעלת מספר סיבובים קבוע עבור שפה שהיא \(\mbox{coNP}\)-שלמה, אז "דברים רעים קורים" ("ההיררכייה הפולינומית קורסת לרמה השניה"). ומערכת הוכחה עבור שפות שהן מחוץ ל-\(\mbox{coNP}\) ו-\(\mbox{NP}\)? גם זה כבר קשה ולא צפוי שנוכל לתת דוגמה פשוטה יותר מהדוגמה-שהיא-כבר-הוכחה של \(\mbox{IP=PSPACE}\).

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

גרף הוא אחד מהמושגים הבסיסיים ביותר במדעי המחשב והצגתי אותו כאן כבר מספרים פעמים. הוא מורכב מקבוצה של צמתים \(V\), ומקשתות, שהן זוגות של צמתים: \(E\subseteq V\times V\). כל זוג צמתים \(u,v\) הוא או מחובר בקשת או שלא. זה הכל; אבל המושג הפשוט הזה ממדל אינספור דברים.

שני גרפים הם איזומורפיים אם הם זהים עד כדי הסימון שאנחנו נותנים לצמתים. אצלנו תמיד נסמן את הצמתים במספרים טבעיים, כלומר \(V=\left\{ 1,2,3,\dots,n\right\} \), ואז שני גרפים \(G_{1}=\left(V_{1},E_{1}\right)\) ו-\(G_{2}=\left(V_{2},E_{2}\right)\) הם איזומורפיים אם קיימת תמורה \(\sigma\) של הקבוצה \(\left\{ 1,\dots,n\right\} \) (תמורה היא סידור מחדש של אברי הקבוצה – פונקציה חד-חד ערכית ועל מהקבוצה לעצמה) כך ש-\(\left(u,v\right)\in E_{1}\) אם ורק אם \(\left(\sigma\left(u\right),\sigma\left(v\right)\right)\in E_{2}\). במילים: שני צמתים בגרף \(G_{1}\) מחוברים בקשת אם ורק אם שני הצמתים ב-\(G_{2}\) שאליהם \(\sigma\) מעבירה אותם גם הם מחוברים בקשת. כרגיל, תמונה אחת שווה אלף מילים:

כאן יש שני גרפים. בשניהם \(V=\left\{ 1,2,3,4\right\} \), אבל בראשון \(E_{1}=\left\{ \left(1,2\right),\left(1,3\right),\left(2,4\right),\left(3,4\right)\right\} \) ובשני \(E_{2}=\left\{ \left(1,2\right),\left(1,4\right),\left(2,3\right),\left(3,4\right)\right\} \). הגרפים הללו "נראים" שונה, אבל הם איזומורפיים: \(\sigma\left(1\right)=1,\sigma\left(2\right)=2,\sigma\left(3\right)=4,\sigma\left(4\right)=3\), ששווה ערך להחלפת צמתים 3 ו-4 (דמיינו שאתם עושים זאת לגרף הראשון בלי "לקרוע" את הקשתות) הוא האיזומורפיזם המתאים.

הבה ונגדיר שפה: \(\mbox{GI}=\left\{ \left(G_{1},G_{2}\right)|G_{1}\cong G_{2}\right\} \) – שפת כל זוגות הגרפים שאיזומורפיים זה לזה. מה אפשר להגיד על השפה הזו? בבירור \(\mbox{GI}\in\mbox{NP}\) – אם יש לנו זוג גרפים איזומורפיים, אז הוכחה לכך היא פשוט \(\sigma\) שמהווה איזומורפיזם; בהינתן \(\sigma\) כזו לא קשה לבדוק את התנאי על הקשתות. האם \(\mbox{GI}\in\mbox{P}\)? זוהי שאלה פתוחה. הייחוד של \(\mbox{GI}\) היא בכך שמאוד לא סביר שהיא \(\mbox{NP}\)-שלמה – יש הוכחה לכך שאם \(\mbox{GI}\) היא \(\mbox{NP}\)-שלמה אז "דברים רעים קורים" (שוב, ההיררכייה הפולינומית קורסת). הרבה יותר סביר שיתגלה ש-\(\mbox{GI}\in\mbox{P}\), אבל לעת עתה, למרות שלפני כמה שנים היה נדמה לרגע שנמצאה לכך הוכחה – זו עדיין שאלה פתוחה.

אבל \(\mbox{GI\ensuremath{\in}NP}\), אז איך היא רלוונטית לדיון בכלל? ובכן, היא לא, אבל השפה המשלימה שלה כן: \(\mbox{GNI}\), שפת כל זוגות הגרפים שאינם איזומורפיים, היא אמנם ב-\(\mbox{coNP}\) אך איננו חושבים שהיא \(\mbox{coNP}\)-שלמה (אם היא הייתה כזו אז \(\mbox{GI}\) הייתה \(\mbox{NP}\)-שלמה) וגם איננו יודעים אם היא ב-\(\mbox{P}\). זה הופך אותה לדוגמה המושלמת עבורנו. אם כן, איך תעבוד מערכת הוכחה אינטראקטיבית לשפה זו? איך להוכיח ששני גרפים אינם איזומורפיים?

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

הפתרון הוא משהו ששונה מאוד באופיו מהוכחות שאנחנו מכירים, ולכן אולי קשה אינטואיטיבית לעיכול. מה שהמוודא יעשה הוא להציב "אתגר" למוכיח – שאלה כלשהי, שהמוכיח יכול לענות עליה אם \(G_{1}\) אינו איזומורפי ל-\(G_{2}\), אבל אם הם איזומורפיים אין למוכיח שום דרך לענות עליה, והוא יצטרך "לנחש" מה המוודא רוצה לשמוע אם הוא מנסה לרמות אותו.

התעלול של המוודא פשוט. בתחילת הדיאלוג, הוא מטיל מטבע בחשאי לעצמו – בחשאי, כלומר באופן שבו המוכיח אינו יודע מה המוודא קיבל בהטלת המטבע. על פי הטלת המטבע המוודא בוחר אחד משני הגרפים – או \(G_{1}\) או \(G_{2}\). כעת המוודא מגריל – שוב, בחשאי – פרמוטציה \(\sigma\), ומפעיל אותה על צמתי הגרף שהוא בחר. התוצאה היא גרף חדש, \(G_{3}\), שאיזומורפי אל… אל מי, בעצם? ברור ש-\(G_{3}\) איזומורפי לגרף שהמוודא בחר, אבל אם \(G_{1}\cong G_{2}\), אז \(G_{3}\) איזומורפי לשני הגרפים גם יחד.

כעת המוודא שואל את המוכיח שאלה פשוטה – מה הגרף שבחרתי בהגרלה? אם \(G_{1}\) אינו איזומורפי ל-\(G_{2}\), אז \(G_{3}\) איזומורפי בדיוק לאחד משני הגרפים הללו. המוכיח הוא בעל כוח חישובי בלתי מוגבל ולכן הוא יכול לבדוק למי משניהם \(G_{3}\) איזומורפי ולענות בהתאם. הוא תמיד יענה נכון, ולכן המוודא יקבל. לעומת זאת, אם \(G_{1}\cong G_{2}\) אז \(G_{3}\) איזומורפי לשניהם, ולכן המוכיח לא מקבל שום אינפורמציה על הגרף שבו המוודא בחר; ומכיוון שהמוודא בחר את הגרף שלו בהסתברות חצי-חצי, אז בכלל לא משנה איך המוכיח בוחר מה לענות לו, המוכיח יצליח לקלוע לבחירה של המוודא רק בהסתברות \(\frac{1}{2}\). כלומר, יש למוודא הסתברות של \(\frac{1}{2}\) לטעות.

כדי להקטין את ההסתברות לטעות, המוודא יכול לשחק את המשחק הזה כמה סיבובים שמתחשק לו. אם הוא משחק \(k\) סיבובים עם המוכיח, ההסתברות שהמוכיח יצליח לעבוד עליו בכל \(k\) הסיבובים היא \(\frac{1}{2^{k}}\) – והדבר הזה שואף מהר מאוד לאפס, בלי להגדיל משמעותית את זמן החישוב של המוודא (פורמלית – יש לנו הקטנה אקספוננציאלית של הטעות במחיר הגדלה פולינומית של זמן הריצה). בקיצור, קיבלנו מערכת הוכחה אינטראקטיבית בדיוק כפי שרצינו – שלמות מלאה, נאותות בהסתברות טובה כרצוננו, וזמן ריצה פולינומי.

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

מערכת הוכחה מאוד דומה באופיה לבעיה אחרת שגם היא ב-\(\mbox{coNP}\) אך איננו יודעים אם היא ב-\(\mbox{P}\) קשורה לבעיית שארית ריבועית. בהינתן מספר \(n\), אומרים ש-\(a\) הוא שארית ריבועית מודולו \(n\) אם קיים פתרון למשוואה \(x^{2}\equiv a\left(\mbox{mod n}\right)\). במילים אחרות, קיים \(x\) כלשהו שכאשר מעלים אותו בריבוע ומחלקים ב-\(n\), השארית המתקבלת שווה לשארית החלוקה של \(a\) ב-\(n\). בדרך כלל מסתפקים בדיון הזה במספרים שהם בין \(0\) ו-\(n-1\).

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

כעת, נניח שהמוכיח רוצה להוכיח למוודא ש-\(a\) כלשהו, שסימן יעקובי שלו הוא 1, איננו שארית ריבועית. אז מערכת הוכחה תתנהל כך: המוודא יגריל מספר כלשהו \(x\) בין \(0\) ל-\(n-1\),יגריל ביט \(b\in\left\{ 0,1\right\} \), ישלח למוכיח את \(a^{b}x^{2}\) וישאל אותו מהו הביט \(b\). איך המוכיח יכול לענות על כך?

ובכן, נניח ש-\(a\) אינו שארית ריבועית. אז \(a^{0}x^{2}=x^{2}\) הוא בוודאי שארית ריבועית; ואפשר להוכיח ש-\(a^{1}x^{2}\) איננו שארית ריבועית (מכיוון ששארית ריבועית כפול משהו שאינו שארית ריבועית, אינו שארית ריבועית). לכן המוכיח (הכל יכול מבחינה חישובית) רק צריך לבדוק אם מה ששלחו לו הוא שארית ריבועית או לא, ולענות 0 או 1 בהתאם. לעומת זאת, אם \(a\) הוא כן שארית ריבועית, אז גם \(x^{2}\) וגם \(ax^{2}\) הם שאריות ריבועיות, ומכיוון ש-\(x\) נבחר באקראי, גם \(x^{2}\) וגם \(ax^{2}\) שניהם שאריות ריבועיות אקראיות כלשהן, ולכן למוכיח לא יהיה מושג מה לענות. אני מניח שהדמיון למערכת ההוכחה של איזומורפיזם הגרפים ברור.

עכשיו אני לא יכול להתאפק ורוצה לעבור לדון בסוג מיוחד של הוכחות אינטראקטיביות – הוכחות באפס ידע. את המושג הזכרתי כבר בראשית ימי הבלוג (לינק), אבל עכשיו זו הזדמנות פז להציג עוד כמה דוגמאות. נתחיל מאיזומורפיזם גרפים – השפה \(\mbox{GI}\), של זוגות גרפים שהם כן איזומורפיים. האם יש דרך שבה המוכיח יוכיח למוודא ש-\(G_{1}\cong G_{2}\)? ובכן, כמובן, הוא יכול פשוט לתת לו את פונקציית האיזומורפיזם, \(\sigma\); אבל האם יש דרך שבה הוא יכול להוכיח זאת למוודא מבלי לגלות לו כלום? כלומר, שהמידע היחיד שהמוודא יסיק מתהליך ההוכחה הוא שאכן \(G_{1}\cong G_{2}\)?

התשובה חיובית, והפתרון פשוט ואלגנטי ביותר. הוא מעין היפוך להוכחה של \(\mbox{GNI}\). המוכיח יגריל פרמוטציה כלשהי \(\pi\), יבחר באקראי אחד משני הגרפים \(G_{1},G_{2}\), יפעיל את הפרמוטציה עליו ויקבל גרף \(G_{3}\), וישלח אותו למוודא. המוודא יגריל מספר \(b\) – או 1, או 2, וישלח אותו למוכיח. המוכיח ישלח לו בחזרה פרמוטציה שהופכת את \(G_{b}\) ל-\(G_{3}\). האם אתם רואים מדוע זו מערכת הוכחה אינטראקטיבית?

אולי אתם תוהים לעצמכם – רגע, מה אפס ידע כאן? הרי המוודא לומד משהו מהפרוטוקול – המוכיח נותן לו איזומורפיזם בין \(G_{b}\) ובין גרף חדש, \(G_{3}\). זה נכון, כמובן, אבל הנקודה היא שהידע הזה הוא משהו שהמוודא היה יכול לייצר בעצמו. מה כבר המוודא קיבל? איזומורפיזם בין אחד מהגרפים המקוריים ובין גרף אקראי כלשהו. גם המוודא יכל לייצר את זה בצורה פשוטה – להגריל \(\pi\), להפעיל אותה על אחד מהגרפים, ולקבל כתוצאה גרף חדש, שנבחר באקראי בין הגרפים שאיזומורפיים ל-\(G_{1},G_{2}\). זו המשמעות של אפס-ידע – המוודא לא לומד שום אינפורמציה שהוא לא יכל לייצר בעצמו. יש לכל זה גם הגדרה מתמטית מדויקת, כמובן, והצגתי את הרעיון שמאחוריה בעבר, אבל לא אחזור עליה כעת.

אוקיי, ומה על מערכות ההוכחה שכבר הצגתי, זו עבור \(\mbox{GNI}\) וזו עבור \(\mbox{QNR}\)? הן בהחלט נראות כמו הוכחות אפס-ידע; כל מה שהמוכיח מוסר למוודא זה ביט יחיד שאומר למוודא את מה שהוא כבר יודע מראש – מה הייתה הבחירה האקראית שלו. אם כן, גם אלו הוכחות אפס-ידע, כן? ממש, ממש לא.

מה הבעיה? שהמוודא יכול לרמות. על פי הפרוטקול של \(\mbox{GNI}\) המוודא צריך לבחור גרף מבין \(G_{!},G_{2}\), להפעיל עליו פרמוטציה כלשהי ולשלוח למוכיח. אבל בואו נניח שיש למוודא גרף \(G_{3}\) שלו עצמו אין מושג למי משני הגרפים הוא איזומורפי אבל הוא יודע שהוא איזומורפי לאחד מהם. איך סיטואציה כזו התרחשה בכלל? לא חשוב – העיקר שהיא עשויה להתרחש. כעת, המוודא יעבוד על המוכיח ובמקום לפעול על פי הפרוטוקול הוא ישלח את \(G_{3}\) למוכיח, והמוכיח יעשה בשבילו את העבודה ויגיד לו לאיזה משני הגרפים \(G_{3}\) איזומורפי. הנה – המוודא למד מידע חדש שלא היה ידוע לו קודם.

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

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

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

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

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

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

בואו נביט שניה בהוכחה מתמטית "אמיתית" – הוכחת אוקלידס לקיום אינסוף ראשוניים. נניח שיש רק מספר סופי של ראשוניים, \(p_{1},\dots,p_{n}\). נתבונן במספר \(p_{1}\cdot p_{2}\cdots p_{n}+1\). הוא אינו מתחלק על ידי אף אחד מהראשוניים \(p_{1},\dots,p_{n}\) ולכן מתחלק על ידי ראשוני שונה מהם. זו כל ההוכחה, ועבור המתמטיקאים בקהל אני בטוח שהיא מספיקה, אבל האם זו הייתה "סדרה סופית של טענות הנובעות זו מזו בעזרת כללי היסק תוך שימוש באקסיומות"? היכן האקסיומות? מיהם כללי ההיסק? גרוע מכך – ההוכחה הזו מבצעת הרבה קפיצות לוגיות שעבור מתמטיקאי הן טריוויאליות אבל עבור מי שמעולם לא ראה אותן הן אסון. למה ש-\(p_{1}\cdots p_{n}+1\) לא יתחלק על ידי אף אחד מהראשוניים \(p_{1},\dots,p_{n}\)? ולמה שהוא כן יתחלק על ידי ראשוני שונה מהם? אלו דברים שדורשים הסבר – למעשה, הוכחה – בפני עצמם. ויקיפדיה העברית מכסה זאת בעזרת "ידע קודם שהוכח קודם לכן", אבל כשקוראים הוכחות אמיתיות לא תמיד ברור בכלל לאיזה ידע קודם ההוכחה מתייחסת. בהוכחות אמיתיות (כאלו שנמצאות בספרי לימוד מתקדמים; בספרי מבוא לרוב ההוכחות יותר ידידותיות) יש המון קפיצות מעל פרטים שרק קורא שבקיא בחומר מסוגל להשלים; קוראים אחרים נאלצים לפנות לעזרה לאתרים כמו MathOverflow ו-MathStackExchange.

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

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

בואו נעבור לדבר באופן טהור על גישתם של מדעי המחשב לכל העסק הזה. עבור מדעני המחשב, "טענה" היא בסך הכל סדרה סופית של תווים מעל א"ב כלשהו (למשל, כזה שבו יש רק שתי אותיות – 0 ו-1; שני אלו מספיקים כדי לקודד כל דבר וזה בדיוק מה שקורה במחשבים). לסדרה סופית כזו של תווים קוראים "מילה", ולקבוצה כלשהי של מילים קוראים "שפה" ומסמנים אותה ב-\(L\) לרוב. היעד של מערכות ההוכחה שלנו הוא להראות עבור מילה \(w\) כלשהי כי \(w\in L\). אם \(L\) היא אוסף כל המחרוזות אשר מקודדות טענות נכונות במתמטיקה ו-\(w\) היא המחרוזת "יש אינסוף זוגות ראשוניים שההפרש בין אברי הזוג הוא 2", הרי שלהראות \(w\in L\) במקרה הזה זה בעצם "להוכיח את השערת הראשוניים התאומים", כך שכל הדיבורים הללו על מילים ושפות לא באמת מגבילות את מה שאנחנו מסוגלים לדבר עליו, אלא רק נותנות לו פורמליזם שנוח עבורנו. לכל שפה תהיה מערכת הוכחה משל עצמה.

את המושג של "תהליך הבדיקה" ממדלים בצורה פורמלית בעזרת אלגוריתם, \(V\) – "המוודא" (מלשון Verifier). למי שהמושג אלגוריתם מעורפל מדי בשבילו, בדרך כלל דורשים ש-\(V\) הוא מודל חישוב קונקרטי מסויים, דוגמת מכונת טיורינג; אלו לא פרטים שיש צורך להיכנס אליהם כאן. \(V\) מקבל כקלט זוג \(\left(w,\pi\right)\), כש-\(w\) היא מילה כלשהי ו-\(\pi\) היא מחרוזת שמטרתה להוות הוכחה לכך ש-\(w\) שייך ל-\(L\). מ-\(V\) אנחנו דורשים שבהינתן קלט \(\left(w,\pi\right)\), \(V\) יסיים מתישהו את ריצתו על הזוג (אם הוא לא עוצר לעולם, כל העסק חסר ערך מבחינתנו), ויגיד "כן" או "לא". כדי שנוכל לומר שהאלגוריתם \(V\) פועל נכון, נצטרך שיקרו שני דברים:

1. שלמות: אם \(w\in L\) אז קיימת הוכחה \(\pi\) כלשהי כך ש-\(V\) מסיים את ריצתו על \(\left(w,\pi\right)\) ואומר "כן".
2. נאותות: אם \(w\notin L\) אז לכל \(\pi\) מתקיים ש-\(V\) מסיים את ריצתו על \(\left(w,\pi\right)\) ואומר "לא".

כלומר, אם \(V\) אומר "כן" הוא בעצם אומר "כן, \(w\in L\) וההוכחה \(\pi\) שכנעה אותי בכך", ואילו אם הוא אומר "לא", הוא בעצם אומר "\(\pi\) לא שכנעה אותי ש-\(w\in L\)" (שימו לב להבדל המהותי בין זה ובין לומר "\(w\notin L\), נקודה").

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

אם כן, עולה השאלה הטבעית – האם השימוש ב-\(\pi\) – האם המעבר מ"\(V\) בודק דברים לבד" ל-"\(V\) מקבל הוכחה מהעולם החיצון ונעזר בה" – מוסיפה למערכת כוח חישובי? התשובה היא – בהחלט כן.

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

כעת, לבעיה העשירית של הילברט יש מערכת הוכחה פשוטה למדי: אם \(w\) משוואה דיופנטית בעלת פתרון, אז \(\pi\) יקודד את הפתרון הזה – ההצבה הנדרשת למשתנים. אם \(V\) מקבל \(\left(w,\pi\right)\), הוא פשוט מציב את \(\pi\) לתוך המשוואה ובודק אם המשוואה מתקיימת או לא. אם כן – האח, \(V\) עוצר ומקבל; אחרת, \(V\) עוצר ודוחה. בכל מקרה \(V\) יעצור, ובכל מקרה הוא לא יטעה – אם ל-\(w\) יש פתרון, אז יש \(\pi\) שעבורו \(V\) יקבל (ההצבה ה"נכונה" למשוואה) ואם ל-\(w\) אין פתרון, ברור שלכל \(\pi\) הוא ידחה.

לא קשה להוכיח טענה כללית על מערכות הוכחה שכאלו – השפות שקיימת להן מערכת הוכחה שכזו הן בדיוק השפות שב-\(\mbox{RE}\). מכיוון ש-\(\mbox{RE}\) גדולה יותר מ-\(\mbox{R}\), זה מראה שמערכת ההוכחה שתיארנו מוסיפה כוח חישובי רב.

המחלקות \(\mbox{R}\) ו-\(\mbox{RE}\) שייכות לעולם המופלא של תורת החישוביות – לשאלה מה ניתן לחשב בכלל. העניינים נהיים סבוכים ומעניינים בהרבה כאשר עוברים לעולם המפלא של תורת הסיבוכיות – שבו השאלה היא מה ניתן לחשב ביעילות, כשכאן "יעילות" מזוהה עם "ריצה בזמן שהוא פולינומי בגודל הקלט". לכן אנחנו מדברים פה על מערכת הוכחה שזהה למה שתיארנו קודם פרט לדרישה ש-\(V\) ירוץ בזמן שהוא פולינומי בגודל של \(w\) (וכפועל יוצא מכך נובע ש-\(\pi\) אף הוא צריך להיות פולינומי בגודל \(w\) אחרת \(V\) לא יספיק לקרוא את כולו).

בעולם החדש הזה המחלקה \(\mbox{P}\) היא המקבילה של \(\mbox{R}\), ולמחלקת השפות שיש להן מערכת הוכחה מהסוג שתיארתי קוראים \(\mbox{NP}\). זו, אם כן, המקבילה של \(\mbox{RE}\) בעולם הסיבוכיותי, וכמו שאפשר להוכיח ש-\(\mbox{R}\ne\mbox{RE}\) ולכן הוכחות מוסיפות כוח באופן כללי, עולה השאלה האם \(\mbox{P}\ne\mbox{NP}\) ולכן הוכחות מוסיפות כוח בהקשר של חישובים יעילים. זו, אולי כבר שמעתם, הבעיה הפתוחה המרכזית במדעי המחשב, ואחת מהבעיות הפתוחות החשובות ביותר במתמטיקה באופן כללי. ההשערה היא שאכן \(\mbox{P}\ne\mbox{NP}\), אבל לכו תוכיחו – העולם הסיבוכיותי מאתגר הרבה יותר מהעולם החישוביותי וכבר נתתי דוגמה לכך בעבר.

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

אינטראקציה אומרת כך – הבה ונניח שלמשחק שלנו מצטרף מתמודד נוסף, \(P\), "המוכיח" (מלשון Prover). בהינתן \(w\) \(P\) ו-\(V\) מנהלים ביניהם דיאלוג כלשהו – \(P\) שולח ל-\(V\) הודעה, ו-\(V\) יכול לענות לו, ו-\(P\) יכול לענות לתשובה, וכן הלאה. בסופו של דבר (ואחרי זמן פולינומי) \(V\) צריך לעצור ולקבל או לדחות את \(w\), ואותם תנאים של קודם תקפים: אם \(w\in L\) אז יש דרך התנהגות של \(P\) שגורמת ל-\(V\) לקבל, ואילו אם \(w\notin L\) אז לא משנה איך \(P\) יתנהג, \(V\) ידחה. בדרך כלל במערכות כאלו אנחנו לא מניחים ש-\(P\) מוגבל חישובית בכלל – כמו שקודם ההוכחה \(\pi\) הגיעה באורח קסום מהשמיים, כך גם כאן \(P\) הוא יצור שמיימי בעל כוח לא מוגבל (בעולם האמיתי הכוח של \(P\) ינבע לרוב מכך שיש לו כבר ידע קודם שאין ל-\(V\); למשל, \(P\) יכיר פירוק לגורמים של מספר \(n=pq\) מסויים בגלל שהוא עצמו הגריל מלכתחילה את \(p,q\) והכפיל אותם לקבלת \(n\)) .

טוב, אז מה נשתנה אם מרשים אינטראקציה? באופן מאכזב למדי, כלום. \(\mbox{NP}\) היא עדיין מחלקת הבעיות שקיימת להן הוכחה, גם עם מוכיח אינטראקטיבי שכזה. הסיבה לכך היא שאת כל מה ש-\(P\) עושה "אינטראקטיבית" אפשר היה לכתוב ב-\(\pi\) מראש, שכן ברור למוכיח בדיוק איך \(V\) הולך להגיב לכל דבר ש-\(P\) יאמר, כי \(V\) הוא דטרמיניסטי. אז ההוכחה תהיה בערך כך: "התשובה לשאלה הראשונה שלך היא: 42. התשובה לשאלה השניה שלך היא: 0. נכון שזה קריפי שאני יודע מה אתה הולך לשאול? נכון? נכון? נכון? טוב, בוא נמשיך, התשובה לשאלה השלישית היא: 42. וואו, השאלות שלך לא מקוריות. טוב, בוא נמשיך…".

איך אפשר להתקדם מכאן? בכמה דרכים. אחת מהדרכים היפות היא מערכת בוררות. במערכת שכזו אין מוכיח אחד אלא שני מוכיחים, שכל אחד מהם רוצה להוכיח משהו שונה. המטרה של אחד מהם היא להוכיח ש-\(w\in L\) והמטרה של השני – ש-\(w\notin L\). ברור שאחד מהם משקר, ולכן הם מנהלים מאבק כלשהו. בינתיים \(V\) יושב בצד ומאזין לויכוח שלהם (הוא לא צריך לשאול שאלות בעצמו כי, כמו קודם, המוכיחים יודעים בדיוק מה הוא הולך לשאול שכן הוא דטרמיניסטי). בסוף הויכוח (שצריך להימשך זמן פולינומי), \(V\) חורץ דין ומחליט האם \(w\in L\) או לא. כרגיל, ל-\(V\) אסור לטעות, בכלל.

האם המערכת הזו מוסיפה כוח? ככל הנראה כן. אפשר להוכיח שמחלקת השפות שיש להן מערכת בוררות שכזו היא \(\mbox{PSPACE}\) – מחלקת כל השפות שניתן להכריע בזכרון פולינומי. \(\mbox{PSPACE}\) היא מחלקה ענקית, שכוללת את \(\mbox{NP}\) וגם הרבה מעבר לכך; אתאר אותה בפוסט הבא יותר בפירוט. מצד שני, אין לנו מושג כיום אם \(\mbox{P}\ne\mbox{PSPACE}\).

הדרך השניה להתקדם מכאן היא להרשות אקראיות. נניח שאנחנו מרשים למוודא לעשות הגרלות שמכתיבות אילו שאלות הוא ישאל את המוכיח. האם שינינו משהו? ובכן, אם כל מה שעשינו הוא להרשות למוודא להגריל שאלות, לא ממש. כי איך תיראה כעת הוכחה \(\pi\) לנכונות טענה? היא תהיה מהצורה "אם היית מגריל 0, אז היית שואל כך וכך, והייתי עונה לך: 42! ואז, אם היית מגריל 1, היית שואל כך וכך והייתי עונה לך: 17! ואחר כך…". כלומר, ההוכחה מתארת מה קורה בסדרת בחירות אקראיות אחת של המוודא ומתעלמת מכל שאר האפשרויות. למה זה עובד? כי בסוף הדיאלוג הזה, התשובה של המוודא חייבת להיות התשובה הנכונה. אם \(w\in L\), כל מה שאנחנו רוצים הוא לראות סדרת בחירות אקראיות אחת שגורמת למוודא להשיב "כן". לא אכפת לנו מכך שיש אולי עוד המון דרכים לגרום לו להשיב כך.

אז כדי לפרוץ את גבולות \(\mbox{NP}\), אנחנו מכניסים לתמונה משהו שנראה כמו חילול הקודש כאשר מדובר על הוכחות – משהו שבאמת משנה לגמרי את התמונה: אנחנו מרשים למוודא לטעות. אנחנו עדיין דורשים שאם \(w\in L\) אז המוכיח יהיה מסוגל לשכנע אותו, ולא משנה מה המוודא שואל; אבל אם \(w\notin L\) אנחנו מרשים למוודא לענות בטעות "כן" בסוף הפרוטוקול. אנחנו רק דורשים שההסתברות לכך תהיה נמוכה. כמה נמוכה? ובכן, כמה שתרצו! אני ארחיב על כך בהמשך. הנקודה היא שלמוודא חייבת להיות הסתברות כלשהי, זניחה ככל שתהיה, לטעות.

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

כמה כוח הוסיפה לנו האפשרות הן לבצע אינטראקיציה והן האקראיות? כלומר, מהי המחלקה \(\mbox{IP}\) של כל השפות שיש להן הוכחה אינטראקטיבית הסתברותית? זו הייתה שאלה פתוחה במשך זמן מה מאז שהוצע המודל. היה ברור לכולם ש-\(\mbox{IP}\subseteq\mbox{PSPACE}\), אבל מה פרט לכך? כשהסתכלו על המחלקות \(\mbox{IP}\left[k\right]\) של מערכות הוכחה שבהן האינטראקציה היא של \(k\) סיבובים בדיוק, התגלה שלא משנה כמה \(k\) גדול – כל עוד הוא קבוע בגודלו ביחס לגודל הקלט, מתקבלת המחלקה \(\mbox{IP}\left[2\right]\). רק כשמרשים למספר הסיבובים בפרוטוקול להיות פולינומי בגודלו ביחס לגודל הקלט יש סיכוי לקבל משהו גדול יותר. מצד שני, אף אחד לא הכיר בעיות שדרשו זאת – כל מה שמצאו לו פרוטוקול הוכחה אינטראקטיבית (ונראה לכך דוגמאות בפוסט הבא) יכל להסתפק במספר קבוע של סיבובים. בנוסף, לא נראה היה שהסתברות אמורה להוסיף הרבה כוח למערכת ההוכחה; הסתברות לא מוסיפה הרבה כוח גם לחישוב רגיל (המחלקה \(\mbox{BPP}\), שהיא המקבילה ההסתברותית של \(\mbox{P}\), איננה גדולה מ-\(\mbox{P}\) בהרבה ויש החושדים ש-\(\mbox{P=BPP}\), ובניגוד ל-\(\mbox{P=NP}\) זה גם לא מופרך).

אם כן, האמונה הרווחת בקרב מדעני המחשב הייתה ש-\(\mbox{IP}\) היא מחלקה חלשה יחסית. ואז ב-1990 הוכיחו ש-\(\mbox{IP=PSPACE}\) (הוכיח את זה עדי שמיר, ה-S שב-RSA, ובאופן בלתי תלוי הוכיחה את זה עוד חבורה שלא אכתוב את כולה). זו באמת הייתה פצצה, בדיוק בגלל ש-PSPACE היא מחלקה כל כך גדולה ו"חזקה". זה היה גילוי מאוד מפתיע גם מבחינה רעיונית – האופן שבו הוכחה אינטראקטיבית היא הרבה, הרבה יותר מאשר הוכחה "קלאסית". וכמובן, ההוכחה של \(\mbox{IP=PSPACE}\) הייתה גם מבריקה בפני עצמה והשתמשה בטכניקות חדשות ביחס למה שהיה קיים אז.

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

בשעה טובה אנו עוברים לתיאור התוצאה השניה ב"תוצאות מפתיעות בסיבוכיות" – הטענה \(\mbox{NL=coNL}\), או בשמה הקליט יותר, משפט אימרמן-סזלפסני (Immerman–Szelepcsényi – אין לי מושג איך לתעתק נכון), ומכאן ואילך – משפט אימרמן. אז על מה מדובר בכלל?

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

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

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

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

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

בואו נעבור לקצת טרמינולוגיה מדוייקת. במקום לדבר כל הזמן על "בעיות", מדעני מחשב מדברים על "שפות". שפה \(L\) היא קבוצה של מילים – מחרוזות סופיות של תווים שמייצגות מידע כלשהו (יכול להיות קידוד של גרף, מספר, קוד של תוכנית מחשב וכדומה – תלוי בהקשר). למשל, אפשר לדבר על השפה שמכילה את כל השלשות \(\left(G,s,t\right)\) של גרף \(G\) עם צמתים \(s,t\) שיש מסלול ביניהם. השפה המשלימה ל-\(L\) מסומנת ב-\(\overline{L}\) – זו שפת כל המחרוזות שאינן ב-\(L\) (מראש אנחנו מניחים שמדובר רק על מחרוזות בינאריות, נאמר, כך שהשאלה מהי "קבוצת כל המחרוזות" שלוקחים משלים ביחס אליה איננה בעייתית). למשל, אם \(L\) היא שפת השלשות \(\left(G,s,t\right)\) שתיארתי קודם, אז \(\overline{L}\) היא שפת השלשות \(\left(G,s,t\right)\) של גרף \(G\) עם צמתים \(s,t\) שאין ביניהם מסלול. אולי תגידו עכשיו שיש גם הרבה מחרוזות שבכלל לא מייצגות שלשה \(\left(G,s,t\right)\) וגם הן אמורות להיות ב-\(\overline{L}\); כדי להיפרד מהמטרד הלא חשוב הזה נוח להניח שכל מחרוזת שמייצגת ג'יבריש תיחשב על ידינו ככזו שמייצגת איזה קלט טריוויאלי – למשל \(\left(G,s,t\right)\) כאשר \(G\) הוא גרף ששני הצמתים היחידים בו הם \(s,t\) ואין קשתות. הדברים הללו לא קריטייים ממילא ולא אחזור אליהם.

אומרים ש-\(L\in\mbox{NP}\) אם קיימת מכונת טיורינג \(M\) (ואם "מכונת טיורינג" לא אומר לכם כלום, תחשבו על "אלגוריתם" ותו לא; הסיבה שאומרים מכונת טיורינג במקום אלגוריתם היא אך ורק מכיוון שאין הגדרה מתמטית פורמלית ל"אלגוריתם") כך שאם \(x\in L\) אז קיים \(y\) כלשהו כך ש-\(M\left(x,y\right)=\mbox{ACCEPT}\), כלומר \(M\), כשהיא רצה על הקלטים \(x,y\) יחדיו, מסיימת את ריצה עם הפלט "Accept"; ואם \(x\notin L\) אז לכל \(y\) \(M\left(x,y\right)=\mbox{REJECT}\), כלומר \(M\) דוחה כל "נסיון הוכחה" לכך ש-\(x\in L\) במקרה שבו \(x\notin L\). יש על \(M\) דרישה אחת נוספת – שזמן הריצה שלה יהיה יעיל – פולינומי – ביחס לגודל של \(x\). הדרישה הזו אוטומטית גם מגבילה את \(y\); אם \(y\) הוא יותר מאשר פולינומי בגודל של \(x\), אז \(M\) פשוט לא תספיק לקרוא את כולו. לכן לפעמים כדי לפשט את החיים דורשים מראש ש-\(y\) יהיה פולינומי ב-\(x\).

כעת אפשר להציג את \(\mbox{coNP}\): בפשטות, זו המחלקה של כל המשלימות של שפות ב-\(\mbox{NP}\): \(\mbox{coNP}=\left\{ \overline{L}|L\in\mbox{NP}\right\} \). כפי שתיארתי לעיל, זו מחלקת השפות שיש עבורן תהליך-בדיקת-עדים כך שעבור תשובת "לא" קיים \(y\) שמוכיח זאת, ועבור תשובת "כן" אין אף \(y\) שיעבוד עלינו ויגרום לנו לחשוב שהתשובה היא "לא". וכעת לשאלת המחץ: האם \(\mbox{NP}=\mbox{coNP}\)?

האם העובדה שקל להוכיח שמשהו הוא "כן" גוררת שיהיה קל להוכיח אם הוא "לא", ולהפך? האם העולם סימטרי ונחמד? זו השאלה. נתון גרף ונשאלת השאלה אם אפשר לצבוע אותו בשלושה צבעים. אם מישהו יתן לי את הצביעה יהיה לי קל לבדוק שהגרף אכן ניתן לצביעה כזו; האם יש דרך פשוטה במידה דומה לשכנע אותי שהגרף לא ניתן לשום צביעה? אםh תוכיחו את זה, הוכחתם כי \(\mbox{NP=coNP}\). אני מקווה שאתם מרגישים את חוסר הסימטריה המשווע שיש כאן; הוא הסיבה לכך שהאמונה הרווחת היא ש-\(\mbox{NP}\ne\mbox{coNP}\).

ייתכן שאתם תוהים מה הקשר של השאלה הזו לשאלה המפורסמת ביותר, האם \(\mbox{P=NP}\) (\(\mbox{P}\) היא מחלקת השפות שניתן להכריע עם אלגוריתם פולינומי שכלל לא נזקק לעדים). ובכן, אם \(\mbox{P=NP}\) אז \(\mbox{NP=coNP=P}\) (וזאת מכיוון ש-\(\mbox{P}\) סגורה למשלים), אבל אם \(\mbox{P}\ne\mbox{NP}\) (וכך סבורים כולם, כמעט) זה לא אומר ש-\(\mbox{NP}\ne\mbox{coNP}\). כך שזו שאלה "עדינה" יותר מאשר \(\mbox{P}\ne\mbox{NP}\) והוכחה עבורה תהיה קשה יותר מאשר הוכחה ש-\(\mbox{P}\ne\mbox{NP}\) (שכן הוכחה ש-\(\mbox{NP}\ne\mbox{coNP}\) תוכיח בפרט ש-\(\mbox{P}\ne\mbox{NP}\)).

עכשיו בואו ונבצע שינוי מחשבתי כלשהו. במקום לדבר על יעילות בצריכת משאב הזמן, נדבר על יעילות בצריכת משאב הזכרון. זמן ריצה נמדד במספר הצעדים שנדרשו לחישוב במודל הסטנדרטי של מכונת טיורינג – איך אפשר למדוד צריכת זכרון? הגישה הנאיבית מדברת על מודל של מכונת טיורינג עם סרט בודד שבו ראשית כל נכתב הקלט, ואחריו אפשר לכתוב עוד דברים לפי הצורך. אפשר להגדיר את כמות הזכרון שהמכונה צורכת בתור האינדקס של התא הקיצוני ביותר שאליו המכונה מגיעה במהלך החישוב (במילים אחרות – אם הזכרון היה סופי, מה כמות הזכרון המינימלית שלא הייתה גורמת לתוכנית להתרסק על הקלט הנתון). הבעיה עם הגישה הזו היא שאם התוכנית רוצה לקרוא את כל הקלט . (אפילו אם אינה רוצה לכתוב שום דבר) היא צריכה ללכת עד לקצה הקלט וזה כבר יניב שסיבוכיות הזכרון שלה היא לפחות \(\Omega\left(n\right)\). אלא שכאשר מדובר על סיבוכיות זכרון, סיבוכיות שנחשבת "יעילה" היא דווקא משהו מסדר גודל לוגריתמי ב-\(n\), ואת זה בשיטה שלנו אי אפשר למדוד בכלל. אז מה עושים?

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

כעת אפשר להכניס לתמונה סוף סוף את \(\mbox{NL}\)- זו מחלקת השפות שקיימת מכונה-בודקת-עדים עבורן שפועלת בסיבוכיות זכרון \(O\left(\log n\right)\). את \(\mbox{coNL}\) מגדירים באותו אופן כמו \(\mbox{coNP}\). לא מדויק עד הסוף לומר שאלו האנלוגים של \(\mbox{NP}\) ו-\(\mbox{coNP}\) כי גם סיבוכיות זכרון של \(O\left(\log^{k}n\right)\) ("פולי-לוגריתמית") נחשבת יעילה; אבל שתי המחלקות הללו הן הבסיס. ולכן זו הפתעה לא קטנה כשמתברר שהאנלוג לשאלת \(\mbox{NP=coNP}\) עבור סיבוכיות זכרון זוכה לתשובה, ותשובה חיובית דווקא – \(\mbox{NL=coNL}\), ויותר מכך – לכל מחלקה דומה של סיבוכיות זכרון עבור חסם סיבוכיות גדול יותר, השוויון עדיין מתקיים (פורמלית, \(\mbox{NSPACE}\left(f\left(n\right)\right)=\mbox{coNSPACE}\left(f\left(n\right)\right)\) לכל \(f\left(n\right)\ge\log n\) שהיא מה שנקרא Space Constructible, כלומר ניתן לחשב את \(f\left(n\right)\) מתוך \(1^{n}\) תוך שימוש ב-\(f\left(n\right)\) זכרון – זו דרישה טכנית שלא ניכנס כעת אליה). הטענה הוכחה בנפרד בידי אימרמן ובידי סזלפסני, ואין לי מושג מי מהם המציא את ההוכחה שאציג כעת (או אפילו אם מישהו מהם המציא אותה ולא שמדובר על המצאה מאוחרת יותר).

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

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

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

לבדוק שיש מסלול מ-\(s\) אל \(t\) בסיבוכיות זכרון יעילה, בהינתן עד לכך, את זה קל לעשות. העד יהיה תיאור המסלול עצמו, ולכן כל המידע שצריך לזכור בכל שלב הוא מה הצומת הנוכחי שלנו, לקרוא את הצומת הבא בתור מהעד, ולבדוק אם אכן יש קשת מהצומת הנוכחי שלנו אל הצומת הבא בתור שהעד מדבר עליו. מכיוון שלייצג צומת או שניים בודדים דורש רק כמות לוגריתמית של זכרון, זה מראה ש-\(\mbox{CON}\in\mbox{NL}\). האתגר הוא להראות ש-\(\mbox{CON}\in\mbox{coNL}\) – שיש עד לכך שלא קיים מסלול מ-\(s\) אל \(t\). איך עושים דבר כזה? התשובה פשוטה – אומרים את האמת, רק האמת, וכל האמת.

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

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

אז מה ראינו? שבזכרון לוגריתמי אפשר לבדוק הוכחה לטענה מהצורה "לפחות \(k\) הצמתים הללו ישיגים מ-\(s\) ב-\(n\) צעדים", ושאם זה משולב בטענה מהצורה "בדיוק \(k\) צמתים ישיגים מ-\(s\) ב-\(n\) צעדים" אפשר להוכיח שמשהו לא ישיג מ-\(s\) ב-\(n\) צעדים. אבל איך אפשר להראות שבדיוק \(k\) צמתים ישיגים מ-\(s\) ב-\(n\) צעדים? ובכן, באינדוקציה על \(n\).

בואו נסמן ב-\(C_{n}\) את מספר הצמתים שישיגים מ-\(s\) לכל היותר ב-\(n\) צעדים. ראשית, ברור ש-\(C_{1}\) ניתן לחישוב באופן עצמאי לגמרי ובלי שום עזרה – פשוט עוברים איכשהו על רשימת הקשתות של הגרף וסופרים כמה מחוברות ל-\(s\). האתגר הוא להראות שאפשר לתת כעד את \(C_{n+1}\) באופן כזה שאם \(C_{n}\) כבר נתון, אפשר לבדוק שהעד נכון. איך עושים את זה?

בואו נעצור לרגע כדי לקחת אוויר ולסכם את מה שראינו עד כה. ראינו כי ניתן להוכיח (באופן שיהיה ניתן לבדיקה בזכרון לוגריתמי) שצומת כלשהו ישיג מ-\(s\) ב-\(n\) צעדים. כמו כן, ראינו כי אם \(C_{n}\) נתון, אז אפשר להוכיח שצומת כלשהו אינו ישיג מ-\(s\) ב-\(n\) צעדים. למעשה, אפשר גם להוכיח באופן דומה מאוד שצומת \(v\) אינו ישיג מ-\(s\) ב-\(n+1\) צעדים – פשוט מוכיחים שאף שכן של \(v\) אינו ישיג מ-\(s\) ב-\(n\) צעדים (ולמי שנזקק לפירוט – ההוכחה כוללת את רשימת כל \(C_{n}\) השכנים שכן ישיגים ואת המסלול שמוביל להם; בזמן שבודקים שההוכחה נכונה גם בודקים שכל אחד מהשכנים הללו אינו שכן של \(v\)).

עכשיו בואו נעצור לרגע ונחשוב – איך כל המרכיבים הללו פותרים לנו את הבעיה של חישוב \(C_{n+1}\)? תנסו לחשוב על זה בעצמכם לרגע. תזכרו שאנחנו כלל לא צריכים להיות חסכוניים בזמן ריצה, רק בזכרון.

התשובה פשוטה: ההוכחה לערך החדש של \(C_{n+1}\) תהיה מורכבת מרשימת כל הצמתים בגרף לפני הסדר, כשאחרי כל צומת ההוכחה או טוענת שהוא ישיג מ-\(s\) ב-\(n+1\) צעדים ומספקת תת-הוכחה שמראה זאת, או טוענת שהוא אינו ישיג מ-\(s\) ב-\(n+1\) צעדים, ומספקת תת-הוכחה שמראה זאת. הגאונות כאן היא בכך שאחרי שאנחנו גומרים עם צומת, אנחנו לא צריכים לזכור אם הוא היה ישיג או לא היה ישיג (זה ידרוש מאיתנו הרבה יותר מדי זכרון לתחזק רשימה כזו) אלא רק להוסיף או לא להוסיף 1 למונה של \(C_{n+1}\) שאנחנו מתחזקים. אחרי שנסיים לקרוא את ההוכחה (שכאמור, אומרת פרטנית מה קורה לכל אחד מהצמתים בגרף), יהיה ברשותנו הערך הנכון של \(C_{n+1}\).

מכאן הפתרון לבעיה טריוויאלי. ההוכחה לכך ש-\(t\) לא ישיג מ-\(s\) ראשית כוללת הוכחות לסדרת הערכים \(C_{1},C_{2},\dots,C_{\left|V\right|}\), ולבסוף היא כוללת הוכחה לכך ש-\(t\) אינו ישיג מ-\(s\) ב-\(\left|V\right|\) צעדים, שמסתמכת על \(C_{\left|V\right|}\). אם \(t\) לא ישיג מ-\(s\) ב-\(\left|V\right|\) צעדים, הוא לא ישיג בכלל (למה?).

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

בפוסטים הקודמים הסברתי מה אומר משפט ברינגטון, וכעת אפשר להגיע לחלק היפה ביותר בכל העניין – ההוכחה שלו. האתגר הוא להראות שכל פונקציה שנמצאת ב-\(\mbox{NC}^{1}\), כלומר ניתנת לחישוב על ידי מעגל בוליאני מגודל פולינומי ועומק לוגריתמי, ניתנת לחישוב על ידי תוכנית מתפצלת מאורך פולינומי וגודל קבוע, ואפילו קבוע "מאוד" – 5, תמיד. הכיוון ההפוך גם נכון – אם פונקציה ניתנת לחישוב על ידי תוכנית מתפצלת שכזו, אז היא ב-\(\mbox{NC}^{1}\), ולכן אנחנו משיגים תוצאה סגורה ויפה – מחלקת הפונקציות שניתנות לחישוב על ידי תוכניות מתפצלות מרוחב קבוע היא בדיוק \(\mbox{NC}^{1}\) – מחלקה גדולה בהרבה ממה שניתן היה לצפות. ההוכחה היא יפה מאוד לטעמי, אבל לא טריוויאלית, ומי שאינו משופשף קצת בהוכחות כאלו בהחלט עלול לאבד אותי.

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

אם כן, אם יש לנו תוכנית מתפצלת מרוחב \(d\) כלשהו ומאורך \(t\), איך בונים מעגל בוליאני שמסמלץ אותה? הרעיון הוא לבנות נוסחה שאומרת "בגרף הזה והזה יש מסלול מהצומת \(a\) לצומת \(b\)" – נסמן נוסחה כזו ב-\(R\left(a,b\right)\). הגרף שעליו מדובר יהיה תמיד הגרף שמתקבל מהתוכנית המתפצלת אחרי שמציבים במשתנים ערכים – אנחנו נראה תכף איך זה בא לידי ביטוי.

את \(R\left(a,b\right)\) קל לבנות במקרה שבו \(a,b\) הם צמתים משכבות סמוכות (הגרף של התוכנית המתפצלת הוא גרף שכבות, זוכרים?). במקרה כזה יש מסלול מ-\(a\) אל \(b\) אם ורק אם יש קשת מ-\(a\) ל-\(b\), מה שמצריך שני דברים: ראשית, שבתוכנית המתפצלת המקורית הייתה קשת מ-\(a\) אל \(b\) (שמסומנת או ב-0 או ב-1) ושנית, שהיא "שרדה" את ההשמה. אם הצומת \(a\) מסומן במשתנה \(x_{i}\), אז נגדיר את הנוסחה באופן הבא: \(R\left(a,b\right)=x_{i}\) אם הקשת \(a\to b\) מסומנת ב-1, \(R\left(a,b\right)=\neg x_{i}\) אם הקשת \(a\to b\) מסומנת ב-0, ו-\(R\left(a,b\right)=0\) אם אין קשת.

נוסחה כללית עבור \(a,b\) שיכולים להיות מרוחקים זה מזה יותר מאשר שכבה אחת נבנית ברקורסיה. הטיעון הבסיסי הוא זה: אם המרחק בין \(a\) ל-\(b\) גדול מ-1 אבל יש מסלול ביניהם, אז יש צומת \(c\) שנמצא "באמצע הדרך" ביניהם. במילים אחרות, יש מסלול מ-\(a\) אל \(b\) אם ורק אם קיים צומת \(c\) בשכבה שהיא באמצע הדרך בין \(a\) ל-\(b\), כך ש-\(R\left(a,c\right)\) וגם \(R\left(c,b\right)\). לאלו מכם שמכירים קצת סיבוכיות כל זה ודאי מזכיר את ההוכחה של משפט סביץ', שמשתמש בתעלול דומה.

מה לכאורה הבעיה? שבשכבת הביניים בין \(a\) ל-\(b\) יכולים להיות המון \(c\)-ים ואז הנוסחה שלנו, שצריכה לקחת בחשבון את כולם, תהיה ענקית. אלא שאנחנו מתעסקים כאן עם תוכניות שהרוחב שלהם חסום, ולכן יש רק \(d\) צמתים \(c\) אפשריים לכל היותר, מה שאומר שהנוסחה שלנו לא תהיה עד כדי כך גדולה. נכתוב אותה במפורש: \(R\left(a,b\right)=\bigvee_{c}\left(R\left(a,c\right)\wedge R\left(c,b\right)\right)\).

נותר להבין מהו גודל הנוסחה. נניח שהמרחק בין \(a\) ו-\(b\) הוא \(k\). נסמן ב-\(S\left(k\right)\) את הגודל המקסימלי של נוסחה שנבנית בשיטה שלנו עבור צמתים במרחק \(k\). אז ראינו כי \(S\left(1\right)\) הוא קבוע קטן, וכי \(S\left(k\right)\le2d\cdot S\left(\frac{k}{2}\right)\) (כי בנוסחה עבור \(R\left(a,b\right)\) שכתבנו, כל \(R\left(a,c\right)\) ו-\(R\left(c,b\right)\) שמופיעים שם עוסקים בזוג צמתים שהמרחק ביניהם הוא בערך \(\frac{k}{2}\) – זאת מכיוון שבחרנו את \(c\) להיות באמצע הדרך). פתרון נוסחת הנסיגה שלעיל מניב ש-\(S\left(k\right)=O\left(\left(2d\right)^{\lg k}\right)=O\left(k^{\lg\left(2d\right)}\right)\), ולכן נקבל שגודל הנוסחה \(R\left(s,t\right)\) עבור התוכנית המתפצלת כולה, גודל המעגל המתאים יהיה \(O\left(t^{\lg\left(2d\right)}\right)\) – זהו פולינום ב-\(t\), שכן \(d\) קבוע. זה סוף הכיוון הזה – עד כה לא ראינו רעיונות מעניינים חריגים.

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

בואו נעשה קצת סדר בעניינים. אצל ברינגטון, כל שכבה בתוכנית המתפצלת כוללת חמישה צמתים בדיוק. נמספר אותם \(1,2,3,4,5\). עכשיו, מהצומת \(1\) יוצאות שתי קשתות – אחת שמסומנת ב-0 ואחת שמסומנת ב-1. הקשת שמסומנת ב-0 נכנסת לאחד מהצמתים בשכבה הבאה, שגם בה כל הצמתים מסומנים ב-1 עד 5. נניח שהקשת נכנסת ל-3, אז אנחנו אומרים ש-"1 עובר ל-3 עם הקשת 0". באותו אופן כל אחד מחמשת המספרים עובר למספר בשכבה הבאה עם קשת ה-0 שלו. ברינגטון מוודא שלא יהיו שני מספרים שעוברים לאותו צומת בשכבה הבאה, ולכן אכן מתקבלת כאן פרמוטציה. באותו אופן, אם שוכחים מהקשתות שמסומנות ב-0 ומסתכלים רק על אלו שמסומנות ב-1, מקבלים פרמוטציה אחרת, אולי שונה מהראשונה.

על כן, אומר ברינגטון, אפשר לאפיין כל שכבה בגרף באמצעות השלשה הבאה: \(\left(k,\pi^{0},\pi^{1}\right)\). \(k\) הוא מספרו של המשתנה \(x_{k}\) אשר מופיע על כל צומת בשכבה הזו. \(\pi^{1}\) היא הפרמוטציה שמתאימה לקשתות שמסומנות ב-0, ו-\(\pi^{1}\) היא הפרמוטציה שמתאימה לקשתות שמסומנות ב-1. בצורה הזו אפשר לבנות את כל התוכנית, ולקבל סדרה של שלשות: \(\left(k_{1},\pi_{1}^{0},\pi_{1}^{1}\right),\left(k_{2},\pi_{2}^{0},\pi_{2}^{1}\right),\dots,\left(k_{t},\pi_{t}^{0},\pi_{t}^{1}\right)\). זוהי תוכנית מאורך \(t\).

כעת, השמה של ערכים למשתנים כמוה בעצם כבחירה של פרמוטציה אחת מכל זוג, והכפלת כל הפרמוטציות שנבחרו כדי לקבל פרמוטציה שמייצגת את הגרף כולו. אם \(\pi\) היא מה שהתקבל מהכפל הזה, אז \(\pi\left(1\right)\) הוא מספרו של הצומת שאליו מגיעים בשכבה האחרונה אם מתחילים את הטיול מצומת 1 בשכבה הראשונה והולכים עם הקשתות שההשמה הותירה בחיים עד שמגיעים לשכבה האחרונה. בדומה \(\pi\left(2\right)\) זה אותו הדבר אם מתחילים מצומת 2 בשכבה הראשונה, וכן הלאה. פורמלית זה מוגדר כך: \(\pi=\prod_{i=1}^{t}\pi_{i}^{x_{k_{i}}}\).

אם כן, אפשר לחשוב על תוכנית מתפצלת \(P\) כעל פונקציה שמקבלת קלט \(\overline{x}\) של ביטים ופולטת פרמוטציה ב-\(S_{5}\): \(P\left(\overline{x}\right)=\pi\). אבל איך כל זה קשור לפלט של 0 או 1? פשוט מאוד: נבחר מראש פרמוטציה ספציפית \(\sigma\in S_{5}\) ששונה מפרמוטציית הזהות, שאותה אסמן ב-\(e\) (הפרמוטציה שמעבירה כל איבר לעצמו). אז נגדיר ש-\(P\) מחזירה 1 על קלט \(\overline{x}\) אם \(P\left(\overline{x}\right)=\sigma\), ושהיא מחזירה 0 אם \(P\left(\overline{x}\right)=e\). בניסוח שיהיה נוח בהמשך – \(P\) \(\sigma\)-מחשבת את \(f\) אם מתקיים הדבר הבא: עבור ערכים של \(\overline{x}\) שעבורם מתקיים \(f\left(\overline{x}\right)=1\), \(P\) מקיימת ש-\(P\left(\overline{x}\right)=\sigma\), ואילו עבור ערכים שעבורם מתקיים \(f\left(\overline{x}\right)=0\), \(P\) מקיימת ש-\(P\left(\overline{x}\right)=e\).

זה שהגדרנו את זה כך זה טוב ויפה אבל לא מתאים להגדרה המקורית של תוכנית מתפצלת – כזכור, תוכנית מתפצלת מחזירה 1 אם יש מסלול מ-\(s\) ל-\(t\) אחרי ההשמה למשתנים, ו-0 אם אין מסלול כזה. אצלנו טרם בחרנו את \(s\) ו-\(t\), והרעיון הוא לבחור אותם באופן שמתאים ל-\(\sigma\). מכיוון ש-\(\sigma\ne e\) קיים \(i\) כך ש-\(\sigma\left(i\right)\ne i\); אם כן, נגדיר את \(s\) להיות הצומת מס' \(i\) בשכבה הראשונה, ואת \(t\) להיות הצומת מס' \(\sigma\left(i\right)\) בשכבה האחרונה, וסיימנו: אם \(P\left(\overline{x}\right)=\sigma\) אז אכן יש מסלול מ-\(i\) אל \(\sigma\left(i\right)\), ואם \(P\left(\overline{x}\right)=e\) אז המסלול היחיד מ-\(i\) הוא אל \(e\left(i\right)=i\ne\sigma\left(i\right)\), כלומר אין מסלול מ-\(s\) אל \(t\).

מסקנת ביניים, למי שאיבד אותי: אנחנו יכולים לשכוח מתוכניות מתפצלות ולעבור לדבר על "תוכניות פרמוטציה" – תוכניות שמתוארת על ידי שלשות של משתנה וזוג פרמוטציות כפי שתיארתי לעיל. מספיק להראות שהן מסוגלות לסמלץ כל מעגל \(\mbox{NC}^{1}\) ולעשות זאת תוך שמירה על אורך לא גדול במיוחד (כלומר, \(t\) קטן).

אולי קצת יותר ברור כעת המספר 5 – הוא אומר שהפרמוטציות שמשתתפות במשחק כולן מ-\(S_{5}\). אבל למה דווקא \(S_{5}\) ולא \(S_{4}\) או \(S_{6}\)? ובכן, עוד מעט נראה.

אמרתי שהסיבה שפרמוטציות מועילות לנו היא כי הן מצד אחד יצורים פשוטים ומצד שני מורכבים – בואו ננסה להבין איך זה מתבטא. ראשית, כמו שכבר ראינו, קיימת פעולת "כפל" של פרמוטציות שפירושה הוא פשוט להפעיל אותן בזו אחר זו: \(\sigma\tau\) זו הפרמוטציה שבה מפעילים את \(\tau\) ואחר כך את \(\sigma\). באופן כללי זה לא חייב להיות שווה ל-\(\tau\sigma\) – נסו למצוא דוגמה שבה אכן \(\tau\sigma\ne\sigma\tau\). כמו כן לכל פרמוטציה קיימת \(\sigma^{-1}\) פרמוטציה הפוכה שעבורה \(\sigma\sigma^{-1}=\sigma^{-1}\sigma=e\). לא קשה לראות שהפרמוטציות מהוות מה שנקרא חבורה עם פעולת הכפל המדוברת, אבל זה לא יהיה קריטי יותר מדי עבורנו כאן.

פרמוטציות פשוטות במיוחד הן מעגלים: אם למשל \(\sigma\left(1\right)=3\) ו-\(\sigma\left(3\right)=5\) ו-\(\sigma\left(5\right)=1\) אז \(\sigma\) כוללת בתוכה את המעגל \(\left(1\ 3\ 5\right)\) ("1 עובר ל-3 שעובר ל-5 שעובר ל-1"). לא קשה להוכיח שכל פרמוטציה אפשר לכתוב כמכפלה של מעגלים זרים, כלומר כאלו שכל מספר מופיע רק באחד מהם. למשל, \(\left(1\ 4\right)\left(2\ 5\right)\left(3\right)\) היא הפרמוטציה שמעבירה את 1 ל-4, את 4 ל-1, את 2 ל-5, את 5 ל-2, ואת 3 לעצמו. אנחנו מדברים על פרמוטציות על חמישה איברים, אז לפרמוטציה שהיא מעגל על כל חמשת האיברים הללו אקרא "5-מעגל" (צריך לא להתבלבל עם המושג השני של מעגל שעליו אנחנו מדברים פה – מעגל בוליאני, שהוא יצור שונה לגמרי – אבל אני בטוח שיהיה בסדר).

פעולה בסיסית בחבורות, ולכן גם בפרמוטציות, היא הצמדה. אם \(\sigma,\tau\) הן שתי פרמוטציות, אז הצמדה של \(\sigma\) על ידי \(\tau\) היא הפרמוטציה \(\tau\sigma\tau^{-1}\). אפשר לחשוב על זה כעל "מה שקורה כשמפעילים את \(\sigma\), אבל לא על הדבר המקורי שעליו רצינו להפעיל אותה אלא עליו אחרי שהוא "מוזז" ובסוף מתקנים את ה"הזזה" הזו" (באלגברה לינארית, למשל, הצמדה של מטריצות היא בעלת המשמעות של שינוי מערכת הקוארדינטות, הפעלת הטרנספורמציה הלינארית שהמטריצה האמצעית מייצגת בתוך מערכת הקוארדינטות החדשה, ואז חזרה למערכת הקוארדינטות הישנה – מי שכל זה נשמע לו כמו ג'יבריש, לא נורא; אני מקווה שהפלתי למישהו אסימון כרגע).

להצמדת פרמוטציות יש פירוש קל ונחמד. בואו נניח לשניה ש-\(\sigma\) היא מעגל: \(\sigma=\left(a_{1}\ a_{2}\ \dots a_{k}\right)\). אז \(\tau\sigma\tau^{-1}=\left(\tau\left(a_{1}\right)\ \tau\left(a_{2}\right)\ \dots\tau\left(a_{k}\right)\right)\). כלומר, עדיין קיבלנו מעגל, רק שבמקום המספרים המקוריים של \(\sigma\) אנחנו מקבלים את המספרים הללו אחרי שערבבנו אותם באופן ש-\(\tau\) מתאר. אם למשל \(\sigma=\left(1\ 4\ 2\right)\) ו-\(\tau=\left(1\ 3\right)\left(2\ 5\right)\) אז \(\tau\sigma\tau^{-1}=\left(3\ 4\ 5\right)\). נסו והיווכחו בעצמכם. לא אוכיח את הטענה הזו כעת למרות שהיא אינה מסובכת במיוחד (האינטואיציה גם כאן היא לחשוב על \(\tau\) כמעין "שינוי קוארדינטות").

המסקנה שמעניינת אותנו כאן היא זו: אם \(\sigma_{1},\sigma_{2}\) הן שתי פרמוטציות ששתיהן 5-מעגל, אז יש \(\tau\) כך ש-\(\tau\sigma_{1}\tau^{-1}=\sigma_{2}\) (למה? האם אתם יכולים להגיד איך מוצאים את \(\tau\)?). בהתבסס על המסקנה הזו, אפשר סוף סוף להתחיל ולראות את הכוח והגמישות שהשימוש בפרמוטציות נותן לנו. נניח ש-\(P\) היא תוכנית פרמוטציות אשר \(\sigma\)-מחשבת איזו פונקציה \(f\), כאשר \(\sigma\) היא 5-מעגל, אז קיימת תוכנית פרמוטציות \(P^{\prime}\) מאותו אורך כמו \(P\) אשר \(\sigma^{\prime}\)-מחשבת את \(f\) לכל \(\sigma^{\prime}\) שהיא 5-מעגל. זה מפחית מאוד את התלות שלנו ב-\(\sigma\)הספציפית שאיתה אנחנו מחשבים את \(f\), וכפי שנראה בקרוב, זה מאוד מועיל.

ההוכחה של הטענה הזו היא פשוט מקסימה. אז נניח ש-\(\sigma^{\prime}=\tau\sigma\tau^{-1}\). בואו נכתוב במפורש את התוכנית \(P\): \(P=\left(k_{1},\pi_{1}^{0},\pi_{1}^{1}\right),\left(k_{2},\pi_{2}^{0},\pi_{2}^{1}\right),\dots,\left(k_{t},\pi_{t}^{0},\pi_{t}^{1}\right)\). מה שנעשה יהיה "לתקן" את \(P\) באופן הבא: \(P^{\prime}=\left(k_{1},\tau\pi_{1}^{0},\tau\pi_{1}^{1}\right),\left(k_{2},\pi_{2}^{0},\pi_{2}^{1}\right),\dots,\left(k_{t},\pi_{t}^{0}\tau^{-1},\pi_{t}^{1}\tau^{-1}\right)\) – כלומר, השינוי הוא רק בפרמוטציות הראשונות והאחרונות. בפרט לא שינינו את אורך התוכנית.

כעת, מה קורה? אם \(f\left(\overline{x}\right)=1\) אז \(P\left(\overline{x}\right)=\prod_{i=1}^{t}\pi_{i}^{x_{k_{i}}}=\sigma\). ומהו \(P^{\prime}\left(\overline{x}\right)\)? ובכן, על פי ההגדרה, זהו \(P^{\prime}\left(\overline{x}\right)=\tau\left(\prod_{i=1}^{t}\pi_{i}^{x_{k_{i}}}\right)\tau^{-1}=\tau\sigma\tau^{-1}=\sigma^{\prime}\).

ואם \(f\left(x\right)=0\), מה אז? ובכן, \(P^{\prime}\left(\overline{x}\right)=\tau\left(\prod_{i=1}^{t}\pi_{i}^{x_{k_{i}}}\right)\tau^{-1}=\tau e\tau^{-1}=\tau\tau^{-1}=e\), שכן כאשר מצמידים את \(e\) תמיד מקבלים את \(e\). קיבלנו בדיוק את מה שרצינו.

הטענה הזו תעזור לנו עוד מעט בהמשך, אבל עכשיו אפשר סוף סוף לגשת להוכחה עצמה. המטרה שלנו היא לבצע סימולציה של מעגל \(\mbox{NC}^{1}\) באמצעות תוכנית פרמוטציות. הרעיון יהיה לתקוף את המעגל באופן אינדוקטיבי – נראה כיצד ניתן להמיר צומת כניסה למעגל לתוכנית פרמוטציות, וכיצד ניתן להמיר את צמתי השערים הלוגיים בתוכניות פרמוטציות. בכל אחד מהמקרים העיקרון יהיה שעל קלטים שעבורם השער פולט \(1\), תוכנית הפרמוטציות תפלוט \(\sigma\) עבור פרמוטציה כלשהי שהיא 5-מעגל, ועל קלטים שעבורם הוא פולט \(0\), תוכנית הפרמוטציות תפלוט \(e\).

כדי לפשוט לנו את החיים, נניח שבמעגל הבוליאני יש רק שני סוגי שערים: שער \(\neg\) ושער \(\wedge\). שער \(\vee\) ניתן לסימולציה בעזרת כללי דה-מורגן: \(x\vee y=\neg\left(\neg x\wedge\neg y\right)\). אמנם, זה יגדיל קצת את עומק המעגל, אבל לא באופן משמעותי – רק פי 2, כלומר הכפלה בקבוע.

נתחיל, אם כן, משער קלט של המעגל. שער כזה תמיד מסומן במשתנה \(x_{i}\) ומקבל 1 או 0 בהתאם לערך ש-\(x_{i}\) מקבל בהשמה. תוכנית פרמוטציות עבור שער כזה היא פשוטה מאוד – מאורך 1: \(P=\left(i,e,\sigma\right)\). נסו להבהיר לעצמכם למה זה עובד.

שער \(\neg\) מסובך מעט יותר ויש בו תעלול נחמד. זכרו שלשער \(\neg\) יש כניסה אחת בלבד, ולכן אפשר לתאר את הסיטואציה כך: יש לנו שער שמחשב פונקציה \(f\) כלשהי וכבר בנינו עבורו תוכנית פרמוטציות \(P\) אשר \(\sigma\)-מחשבת את \(f\) עבור \(\sigma\) שהיא 5-מעגל כלשהו. כעת אנו רוצים לבנות תוכנית פרמוטציות \(\neg P\) אשר \(\tau\)-מחשבת את \(\neg f\) עבור \(\tau\) שגם היא 5-מעגל (לא בהכרח שווה ל-\(\sigma\)). הרעיון הוא זה: אם \(P=\left(k_{1},\pi_{1}^{0},\pi_{1}^{1}\right),\dots,\left(k_{t},\pi_{t}^{0},\pi_{t}^{1}\right)\) אז \(\neg P=\left(k_{1},\pi_{1}^{0},\pi_{1}^{1}\right),\dots,\left(k_{t},\pi_{t}^{0}\sigma^{-1},\pi_{t}^{1}\sigma^{-1}\right)\). כלומר, שינינו במעט את השלב האחרון בתוכנית – שימו לב כי לא שינינו את אורך התוכנית כלל. למה זה עובד? כי אם \(f\left(\overline{x}\right)=1\) אז \(P\left(\overline{x}\right)=\sigma\) ולכן \(\neg P\left(\overline{x}\right)=\sigma\cdot\sigma^{-1}=e\), בהתאם לכך ש-\(\neg f\left(\overline{x}\right)=0\); ואילו אם \(f\left(\overline{x}\right)=0\) אז \(P\left(\overline{x}\right)=e\) ולכן \(\neg P\left(\overline{x}\right)=e\cdot\sigma^{-1}=\sigma^{-1}\). כלומר, \(\neg P\) \(\sigma^{-1}\)-מקבלת את \(\neg f\), וזה מצויין כי אם \(\sigma\) היא 5-מעגל, כך גם \(\sigma^{-1}\) (כלומר, \(\sigma^{-1}\) היא ה-\(\tau\) שלנו).

עכשיו הגענו לקליימקס – שער \(\wedge\). נניח שיש לנו את \(f_{1},f_{2}\) אשר \(\sigma_{1},\sigma_{2}\)-מחושבות בידי \(P_{1},P_{2}\) בהתאמה – ושוב, \(\sigma_{1},\sigma_{2}\) שתיהן 5-מעגלים. אנחנו רוצים לבנות \(P\) אשר \(\sigma\)-תחשב את \(f_{1}\wedge f_{2}\). מה עושים?

כאן נשלף תעלול נוסף: ב-\(S_{5}\) יש שתי פרמוטציות \(\sigma_{1},\sigma_{2}\) שהן 5-מעגלים וגם \(\sigma=\sigma_{1}\sigma_{2}\sigma_{1}^{-1}\sigma_{2}^{-1}\) – מה שנקרא הקומוטטור של \(\sigma_{1},\sigma_{2}\) – הוא 5-מעגל. לעובדה הזו יש חשיבות קריטית, והיא הסיבה שבגללה מתעסקים עם \(S_{5}\) דווקא – עבור \(S_{n}\) עם \(n\le4\) פשוט לא קיימות שתי פרמוטציות שהן מעגלים וגם הקומוטטור שלהן הוא מעגל מאותו האורך.

מיהן אותן תמורות שמקיימות את התכונה המדוברת? ובכן, למשל: \(\left(1\ 2\ 3\ 4\ 5\right)\) ו-\(\left(1\ 3\ 5\ 4\ 2\right)\) שהקומוטטור שלהן הוא \(\left(1\ 3\ 2\ 5\ 4\right)\). לא צריך יותר מזה.

אנחנו יכולים להניח כי \(P_{1},P_{2}\) אכן מחשבות את הפונקציות שלהן בעזרת אותן \(\sigma_{1},\sigma_{2}\) המדוברות בזכות הטיעון שהראינו קודם – שאפשר להחליף בחופשיות את ה-\(\sigma\) של התוכנית כל עוד ממשיכים לדבר על 5-מעגלים. יותר מזה: אנחנו גם יכולים לבנות מ-\(P_{1}\) תוכנית חדשה, \(P_{1}^{-1}\), שאורכה זהה לזה של \(P_{1}\) אבל היא \(\sigma_{1}^{-1}\)-מקבלת את \(f_{1}\). כנ"ל עבור \(P_{2}\). וכעת אפשר להציג את התוכנית עבור \(f_{1}\wedge f_{2}\): היא תהיה פשוט \(P=P_{1}P_{2}P_{1}^{-1}P_{2}^{-1}\). כלומר, שרשור של הסדרות של כל ארבע התוכניות הללו. כאן, סוף כל סוף, אורך התוכנית שאנו בונים גדל.

מדוע זה עובד? ובכן, אם \(f_{1}\left(\overline{x}\right)=f_{2}\left(\overline{x}\right)=1\) אז \(P\left(\overline{x}\right)=\sigma_{1}\sigma_{2}\sigma_{1}^{-1}\sigma_{2}^{-1}=\sigma\), כפי שרצינו. אבל אם למשל \(f_{1}\left(\overline{x}\right)=0\) ו-\(f_{2}\left(\overline{x}\right)=1\) אז \(P_{1}\left(\overline{x}\right)=P_{1}^{-1}\left(\overline{x}\right)=e\) ולכן \(P\left(\overline{x}\right)=e\cdot\sigma_{2}\cdot e\cdot\sigma_{2}^{-1}=e\). באופן דומה מקבלים \(e\) גם עבור הסיטואציות שבהן \(f_{2}\left(\overline{x}\right)=0\). זה הסוף. אני לא יודע מה איתכם, אבל לדעתי הטריק הזה ממש מקסים, ואלוהים יודע מאיפה הוא הגיע.

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

כפי שכבר ראינו, אורך תוכנית שמתאימה לשער קלט היא 1, ושער שלילה לא משנה כלל את אורך התוכנית. רק שער \(\wedge\) מאריך אותה. בואו נסמן ב-\(S\left(d\right)\) את האורך המקסימלי של תוכנית עבור מעגל מעומק \(d\).

אם יש לנו בתוכנית שער \(\wedge\) בעומק \(d\), אז שני הצמתים שנכנסים אליו מהווים כל אחד מעגל בעומק \(d-1\). לכן גודל התוכניות \(P_{1},P_{2}\) עבורם הוא לכל היותר \(S\left(d-1\right)\) לכל אחד מהם. מכיוון שאנו משרשרים את \(P_{1},P_{2}\) ואז גם את שתי התוכניות עם הפרמוטציה ההופכית, אנחנו בסך הכל מגדילים פי 4 את האורך לכל היותר, כלומר \(S\left(d\right)=4\cdot S\left(d-1\right)\). אם נפתור את נוסחת הנסיגה הזו נקבל \(S\left(d\right)=4^{d}\). שזה, חייבים להודות, לא נראה מרשים במבט ראשון – זה נראה אקספוננציאלי.

אלא מה, צריך לזכור שאנו מדברים כאן על מעגל \(\mbox{NC}^{1}\) – מעגל שהעומק שלו הוא לוגריתמי ב-\(n\), כלומר במספר הביטים שעליהם פועלת הפונקציה שמחשבים. לכן \(4^{d}\) הוא בעצם \(O\left(4^{\log n}\right)=O\left(n^{\log4}\right)\) – פולינומי לגמרי (אבל, אם ניקח מעגל \(\mbox{NC}^{2}\), שבו העומק הוא \(O\left(\log^{2}n\right)\), כבר לא נקבל אורך פולינומי). זה מסיים את ההוכחה.

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