משפט ברינגטון - ההוכחה

בפוסטים הקודמים הסברתי מה אומר משפט ברינגטון, וכעת אפשר להגיע לחלק היפה ביותר בכל העניין - ההוכחה שלו. האתגר הוא להראות שכל פונקציה שנמצאת ב-\( \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) \), כבר לא נקבל אורך פולינומי). זה מסיים את ההוכחה.

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