כיצד אורקלים מנבאים שקשה להוכיח ש-P שונה מ-NP

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

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

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

לא הבנתם כלום? מצויין, ההמשך עוד יותר מבלבל.

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

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

אלא מה? כל מה שזה מראה הוא ש-\( \mbox{NP}\subseteq\mbox{P}^{L} \) (כש-\( L \) היא השפה של האורקל שלנו). אנחנו רוצים להראות ש-\( \mbox{NP}^{L}\subseteq\mbox{P}^{L} \) - כלומר, שגם אחרי שמחזקים את המכונות האי-דטרמיניסטיות עם האורקל של \( L \), עדיין מכונות דטרמיניסטיות מצליחות לעשות את אותם הדברים. אלא שזו לא בעיה אמיתית, כי אותה מכונה \( M^{\prime} \) שמסמלצת את המכונה האי דטרמיניסטית \( M \) יכולה לסמלץ גם קריאות לאורקל - כלומר, לבצע בעצמה את החישוב שהאורקל מבצע, על איזה קלט שלא יהיה ש-\( M \) תזרוק עליו, ולענות במקום האורקל. זה לא יגדיל את זמן הריצה של \( M^{\prime} \) בצורה משמעותית (כאן צריך לבוא נימוק טכני מפורט יותר, אך אמנע ממנו - זה תרגיל טוב לחשוב מה בדיוק צריך לומר ואיזה עוד סיבוכים עשויים לצוץ; למשל, האם \( M \) יכולה לקרוא לאורקל עם קלטים שבהם \( 1^{n} \) הוא “גדול מדי”?).

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

בואו ניקח שפה \( L \) כלשהי. לשפה הזו ניתן להתאים שפה אחרת, \( U_{L} \), של אורכי המילים ב-\( L \) (שוב, בייצוג אונרי). במילים אחרות, בהינתן מספר \( 1^{n} \) השאלה היא האם קיימת מילה מאורך \( n \) בשפה \( L \). זו שאלה שקל מאוד להכריע אם אנחנו מכונה אי דטרמיניסטית עם אורקל לשפה \( L \): בהינתן \( n \) פשוט מנחשים מילה מאורך \( n \), שואלים את האורקל האם היא שייכת ל-\( L \) ואם כן - מקבלים. אם כן, לכל שפה \( L \) מתקיים ש-\( U_{L}\in\mbox{NP}^{L} \). מצד שני, מכונה דטרמיניסטית פולינומית לא יכולה לנקוט בגישה הזו - אם נותנים לה \( n \), לבדוק את כל המילים מאורך \( n \) ייקח לה יותר מדי זמן כי יש \( 2^{n} \) כאלו. זה נותן פתח לתקווה לכך שיתקיים \( U_{L}\notin\mbox{P}^{L} \) עבור שפה \( L \) שתהונדס בצורה מתאימה. כמו שכל מי שמכיר קצת את תורת הסיבוכיות יודע, להוכיח שמשהו הוא קשה זה עניין קשה, והבניה של \( L \) היא יצירתית למדי ומסתמכת - איך לא - על לכסון.

הבה ונמספר את כל מכונות הטיורינג הדטרמיניסטיות עם אורקל הקיימות - \( M_{1},M_{2},M_{3},\dots \). מה שנעשה יהיה לבנות את \( L \) בשלבים, כשבשלב ה-\( i \) ננסה לגרום למכונה \( M_{i} \) לטעות בתשובה שהיא אמורה לתת על מילה כלשהי מ-\( L \).

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

ה”סכנה” שבדרך הפעולה שלנו היא ש-\( M_{i} \) עלולה לשאול את האורקל שאלה על כל המילים מאורך \( n \). זה אולי נשמע מוזר קצת בהתחלה - לא אמרנו שנדרש זמן אקספוננציאלי כדי לעשות זאת? אבל זו הנקודה העדינה המרכזית בהוכחות מהסוג הזה - אנחנו תוקפים את \( M_{i} \) עבור \( n \) ספציפי, בעוד שדיבורים על זמן ריצה אקספוננציאלי הם רלוונטיים רק כשמדברים על ההתנהגות האסימפטוטית של \( M_{i} \), כלומר על האופן שבו \( M_{i} \) מתנהגת על אינסוף קלטים. ייתכן שעל כל הקלטים עד גודל זיליארד \( M_{i} \) דורשת פרק זמן גדול עד להדהים, ורק לאחר מכן היא “נרגעת” ורצה זמן פולינומי - גם אז היא עדיין תיחשב פולינומית. מכאן שהסכנה ש-\( M_{i} \) תבדוק את כל המילים מאורך \( n \) היא מוחשית מאוד, ונדרשים פיתולים טכניים כדי להתגבר עליה. במקרה שלנו, פשוט נגביל את זמן הריצה של \( M_{i} \) - אם היא רצה יותר מ-\( \frac{2^{n}}{10} \) צעדים, פשוט נשכח ממנה ונעבור למכונה הבאה. עוד מעט אסביר איך אפשר להבטיח שזה לא יגרום נזק להוכחה שלנו.

אם \( M_{i} \) עצרה על \( 1^{n} \) תוך לכל היותר \( \frac{2^{n}}{10} \) צעדים, אז בהכרח היא לא הספיקה לשאול את האורקל על כל הקלטים מאורך \( n \). אם \( M_{i} \) קיבלה, הרי שהיא טוענת שב-\( L \) יש מילה מאורך \( n \), אולם כרגע בבניה שלנו אין מילה כזו. זכרו - \( n \) היה מספר שגדול מאורך כל המילים שהחלטנו אם הן ב-\( L \) או לא בתחילת הסיבוב \( i \), ובמהלך הסיבוב עצמו לא הוספנו אף מילה ל-\( L \) - בכל פעם ש-\( M_{i} \) שאלה את האורקל על מילה חדשה, אמרנו לה שאותה מילה אינה ב-\( L \). מכאן ש-\( M \) טועה. אם לעומת זאת \( M \) דחתה את \( 1^{n} \), כלומר טענה שאין ב-\( L \) מילה מאורך \( n \), פשוט נוסיף ל-\( L \) מילה כלשהי ש-\( M_{i} \) לא הספיקה לשאול את האורקל עליה (כאמור, יש כזו). ושוב, \( M \) טועה, והגדלנו את \( L \) במילה אחת בסך הכל, כך ש-\( L \) עדיין סופית.

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

ובכן, נניח ש-\( M \) היא מכונה דטרמיניסטית פולינומית שכזו, ושזמן הריצה שלה חסום על ידי הפולינום \( p\left(n\right) \). אז קיים \( n \) גדול מספיק כך ש-\( \frac{2^{n}}{10}>p\left(n\right) \). במילים אחרות, אם ננסה “לתקוף” את \( M \) עבור המילה \( 1^{n} \) או מילים ארוכות יותר, ננצח. איך אפשר להבטיח שאכן נתקוף את \( M \) מתישהו עם מילה ארוכה שכזו? תעלול פשוט - במקום לתקוף את \( M \) פעם אחת, נתקוף אותה אינסוף פעמים. כלומר, המניה \( M_{1},M_{2},M_{3},\dots \) לא תכיל כל מכונה רק פעם אחת, אלא מספר אינסופי של פעמים. קל להנדס מניה שכזו - למשל, הביטו בסדרה \( 1,1,2,1,2,3,1,2,3,4,\dots \) שבה מובטח שכל מספר טבעי יופיע מספר אינסופי של פעמים. מכאן שאנו נתקלים ב-\( M \) בתור \( M_{i} \) עבור אינסוף ערכים שונים של \( i \), ומכיוון שדרשנו שה-\( n \) שאותו בוחרים בסיבוב ה-\( i \) יהיה בפרט גדול מ-\( i \), מובטח לנו שהחל מסיבוב מסויים ה-\( n \) שאיתו נתקוף את \( M \) אכן יביס אותה.

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