תוכניות מתפצלות ומשפט ברינגטון

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

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

כרגיל, תמונה אחת שווה אלף מילים. הנה תוכנית מתפצלת עבור הפונקציה \( \mbox{MAJORITY}\left(x_{1},x_{2},x_{3}\right) \) שמחזירה את הערך הבוליאני שמצוי אצל רוב הקלטים. נסו “לסמלץ” את הריצה של התוכנית על כמה קלטים ובדקו מה קורה.

אולי אתם תוהים למה הגדרתי הגדרה מסובכת שכזו לתוכנית מתפצלת - כל העסק עם מחיקת הקשתות ועם “אם קיים מסלול…”. למה לא אמרתי פשוט “בהינתן קלט נצא לטיול בגרף - כאשר אנחנו בצומת \( x_{i} \) נתבונן בערך המשתנה \( x_{i} \) והצעד הבא שלנו ייקבע על פי ערך זה, ואם אין לנו קשת יוצאת מתאימה ניתקע”? ובכן, זה אכן מספיק עבור מה שנתעסק בו, אבל באופן כללי ייתכן שמאותו צומת תצא יותר מקשת אחת שמסומנת ב-1 (או יותר מקשת אחת שמסומנת ב-0) וכל מה שיעניין אותו הוא שקיימת דרך כלשהי להגיע מ-\( s \) אל \( t \). מי שזה מבלבל אותו - לא נורא, אתם בהחלט יכולים לחשוב על ההגדרה שהצגתי כרגע כאילו היא הגדרה שקולה.

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

כדי להוכיח חסמים תחתונים על מודל חישובי, צריך קודם כל להגדיר מדדי סיבוכיות כלשהם עבורו. אם אנחנו רוצים להגיד “קשה לחשב את \( f \) בעזרת תוכניות מתפצלות” צריך קודם כל להבהיר מה זה בכלל אומר, “קשה”, בהקשר של תוכניות מתפצלות. המדד האלמנטרי הוא הגודל של התוכנית - מספר הצמתים שבה. מחשב אמיתי שרוצה להריץ תוכנית מתפצלת צריך לזכור את כל הצמתים שלה - ולכן מספר אקספוננציאלי של צמתים (כתלות במספר הביטים של הקלט לפונקציה שאותה רוצים לחשב) הוא לא ריאלי - חשבו על תוכנית שכדי לחשב את הפלט של פונקציה על 50 ביטים דורשת \( 1,125,899,906,842,624 \) שורות קוד! (\( 2^{50} \)). לכן הדרישה האלמנטרית מתוכנית מתפצלת הוא שגודלה יהיה פולינומי. כמו שקרה עם מעגלים בוליאניים, כך גם כאן, תוכנית מתפצלת תמיד מוגדרת עבור מספר נתון של ביטי קלט. לכן מדברים לרוב על משפחות של פונקציות, שמחושבות על ידי משפחות של תוכניות מתפצלות, והשאלה ששואלים היא כמה מהר צומח הגודל של התוכנית המתפצלת עבור קלט מאורך \( n \) כאשר מגדילים את \( n \). לא אחזור שוב על הדיון הזה בשלמותו.

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

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

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

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

כדי להבהיר את הקושי כדאי לשכוח שנייה מתוכניות מתפצלות ולדבר על מה שקורה למודל החישובי הסטנדרטי, מכונת טיורינג, אם דורשים מהזכרון שלה להיות חסום באופן שאינו תלוי בקלט. מה שמקבלים הוא שקילות למודל פשוט בהרבה, שמכונה אוטומט סופי דטרמיניסטי. לא אציג את המודל הזה כרגע, אבל רק אבהיר עד כמה הוא חלש: אם נותנים לו מספר, הוא לא מסוגל לבדוק האם המספר ראשוני. אם נותנים לו מחרוזת מהצורה \( 0^{*}1^{*} \) (סדרת אפסים ואז סדרת אחדות - הכוכבית מציינת “0 או 1 או 2 או…”) הוא לא מסוגל לבדוק האם מספר האפסים שווה למספר האחדות. אם נותנים לו שלשה \( \left(a,b,c\right) \) הוא לא מסוגל לבדוק האם \( c=a-b \) (זה בעצם נובע מיידית ממה שאמרתי קודם…). זה מודל מאוד, מאוד חלש. ותוכניות מתפצלות מרוחב קבוע הן בדיוק האנלוג המתאים לאוטומטים סופיים דטרמיניסטיים בתוך עולם התוכניות המתפצלות.

כדי להראות חסם תחתון על תוכניות מתפצלות, כדאי לתקוף קודם כל פונקציה קונקרטית אחת ולהראות שהיא קשה. עבור מעגלים בוליאניים הצליחו להשתמש ב-\( \bigoplus \) (שמבצעת XOR של כל הביטים שלה) בתור פונקציה שכזו - הוכיחו כי היא אינה ב-\( \mbox{AC}^{0} \) (מעגלים בוליאניים מעומק קבוע - שוב ה”קבוע” הזה - עם דרגת כניסה לא מוגבלת של הצמתים). אחרי שיש דוגמה קונקרטית אחת ביד, אפשר לרוב להראות עבור פונקציות רבות אחרות שהן לא שייכות למחלקה על ידי טיעון בסגנון “אם הן כן היו שייכות, אפשר היה להשתמש בהן כדי לחשב גם את \( \bigoplus \)”. לרוע המזל, את \( \bigoplus \) קל מאוד לחשב עם תוכנית מתפצלת מרוחב 2: קוראים ביט ביט, וכל המידע שצריך לזכור הוא “האם סכום הביטים עד כה היה 0 או 1 מודולו 2”. הנה התוכנית המתפצלת המתאימה עבור \( \bigoplus\left(x_{1},x_{2},x_{3},x_{4},x_{5}\right) \):

ובכן, מי כן מועמד טוב להיות פונקציה שתוכניות מתפצלות לא יכולות לחשב? רצוי שזו תהיה פונקציה פשוטה, כזו שאפשר לחשב ביעילות במודלים פשוטים אחרים - זכרו שבסופו של דבר אנחנו רוצים להצביע על קושי של בעיות שנראות פשוטות יחסית (זהו למשל העניין בשאלת \( \mbox{P=NP} \); המחלקה \( \mbox{NP} \) מורכבת מבעיות שבמובן מסויים הן קלות, ולכן חשוב לנו להוכיח שלמרות זאת הן קשות; את זה שקיימות בכלל בעיות שאינן ב-\( \mbox{P} \) קל להוכיח). לצורך העניין, מחלקה פשוטה מספיק שעדיין נראית כמו כר מתאים לחיפוש אחר פונקציות קשות לחישוב היא \( \mbox{NC}^{1} \) - מה שבא בתור אחרי \( \mbox{AC}^{0} \). ב-\( \mbox{NC}^{1} \), כזכור, נמצאות כל הפונקציות שניתנות לחישוב על ידי מעגל מעומק לוגריתמי וגודל פולינומי, שבו דרגת הכניסה של כל שער היא לכל היותר 2. הרבה פונקציות פשוטות (למשל, הפונקציות האריתמטיות) נמצאות שם; וגם הפונקציה \( \mbox{MAJORITY} \) שהזכרתי בהתחלה. אותה \( \mbox{MAJORITY} \) נראתה כבעלת פוטנציאל רב לתקיפת תוכניות מתפצלות; כמו שאפשר לראות בתוכנית המתפצלת שציירתי בהתחלה, נראה שהרוחב תלוי בצורה חזקה בכמות המשתנים. ובאמת, צריך “לזכור” כמה משתנים היו 0 וכמה משתנים היו 1 עד כה, או לפחות מה היה ההפרש ביניהם, והוא יכול להיות גדול באופן שרירותי, לא? זה לא נראה כמו משהו שאפשר לתפוס עם תוכניות מתפצלות מרוחב קבוע. זה הוביל להשערה בראשית שנות השמונים לפיה כל תוכנית מתפצלת מרוחב חסום עבור \( \mbox{MAJORITY} \) לא תהיה פולינומית באורכה. די מהר הוכיחו גם חסם תחתון נאיבי יחסית - שתוכנית מתפצלת מרוחב חסום עבור פונקציה זו לא יכולה להיות לינארית באורכה (כלומר, \( O\left(n\right) \)). על פניו כיוון המחקר הזה נראה מבטיח.

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