אז מדוע קשה להוכיח ש-P שונה מ-NP? (בלכסון)

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

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

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

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

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

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

הרעיון בהוכחה הוא זה: אם יש לנו שתי מחלקות \( A,B \) של שפות (“שפה”היא פשוט אוסף של קלטים - נניח, אוסף הקלטים שעליהם המכונה עוצרת ואומרת “כן”) ואנו רוצים להראות כי \( A\ne B \), וכמו כן \( A \) בבירור מוכל ב-\( B \), אז דרך אחת להראות זאת היא על ידי הצגת מכונה ששפתה נמצאת ב-\( B \), אבל היא מתנהגת באופן שונה מאשר כל מכונה ששפתה ב-\( A \). מה ה”לכסון”כאן? ובכן, זכרו שבהוכחת האלכסון של קנטור התעלול היה לבנות מספר ממשי ש”מתנהג באופן שונה” מאשר כל מספר ממשי שהיה קיים במספור של הממשיים - כלומר, הוא נבדל מכל אחד מהמספרים הללו באחד מהמקומות בפיתוח העשרוני שלהם. כאן זה אותו רעיון: אם \( U \) היא המכונה שאנו בונים ו-\( M \) היא מכונה כלשהי ששפתה ב-\( A \), אז יהיה קיים קלט \( x \) שעליו \( U \) ו-\( M \) יתנהגו שונה (ובפרט לכל \( M \) יהיה מדובר על \( x \) אחר).

כאשר \( A=\mbox{R} \) ו-\( B=\mbox{RE} \), אז המכונות ששפתן ב-\( A \) הן “מכונות שעוצרות תמיד” ואילו מכונות ששפתן ב-\( B \) הן “מכונות שעוצרות תמיד אם התשובה היא “כן”, ואחרת יכולות לא לעצור”. במילים אחרות, המכונה \( U \) שנבנה יכולה לא לעצור על קלטים מסויימים, ואז מובטח שהם לא יהיו בשפה שלה.

כעת הבניה של \( U \) היא פשוטה ביותר: בהינתן קלט \( x \), \( U \) מפרשת אותו כמכונה \( M_{x} \), מריצה את \( M_{x} \) על הקלט \( x \) עצמו, ואם \( M_{x} \) עצרה וענתה - היא עונה הפוך ממנה. מכיוון שכל \( M \) ששפתה ב-\( \mbox{R} \) מחוייבת לעצור, מובטח לנו ש-\( U \) תענה הפוך מכל \( M \) כזו על הקלט \( \left\langle M\right\rangle \) עצמו (הסוגריים המשולשים באים לציין שמדובר על הקידוד של \( M \) כמחרוזת). כמובן ש-\( U \) עלולה לא לעצור כלל אם המכונה \( M_{x} \) שהיא מסמלצת היא מהסוג שלא עונה אף פעם - אבל זה בסדר, כי הרשינו ל-\( B \) להתנהג כך.

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

שימו לב שכעת \( U \) שלנו צריכה לעצור תמיד, אחרת ייתכן ששפתה לא תשתייך ל-\( \mbox{R} \). במילים אחרות, תמו ימי הנעורים הפרועים שבהם \( U \) יכלה פשוט להריץ כל מכונת טיורינג עם כל קידוד שהוא, כי ייתכן שחלק מהמכונות שהיא מריצה לא יעצרו לעולם. כאן נכנס לתמונה התעלול הטכני - \( U \) תפרש את הקלט \( x \) כמכונה כמו קודם, אבל תריץ את \( M_{x} \) על \( x \) רק במשך \( 2^{\left|x\right|} \) צעדים - שתיים בחזקת האורך של \( x \) צעדים (זכרו - \( x \) היא מחרוזת). אם בפרק הזמן הזה \( M_{x} \) עצרה על \( x \), הרי ש-\( U \) תענה הפוך ממנה; ואחרת, פשוט תדחה. מה שאנו מתבססים עליו כאן הוא שלכל מכונה יש אינסוף קידודים מאורכים שונים ומשונים, כי תמיד אפשר להכריז שאם תו מסויים מופיע בקידוד פשוט מתעלמים ממנו (למי שזה מפריע לו - יש עוד דרכים, טיפה פחות אלגנטיות, לעקוף את הבעיה הזו).

כעת מגיע החלק המסובך - נניח שיש מכונה \( M \) שפועלת בזמן ריצה פולינומי, נניח עם פולינום \( p\left(n\right) \). אז קיים \( m \) טבעי כלשהו כך ש-\( p\left(m\right)<2^{m} \) - זה מכיוון שפונקציה מעריכית כמו \( 2^{x} \) גדלה מהר יותר מכל פולינום (טענה שדורשת הוכחה אך אינה מסובכת). בואו ניקח בתור \( x \) עותק של \( M \) שאורכו לפחות \( m \) - כעת מובטח לנו שכאשר \( U \) תרוץ על \( x \) היא תסמלץ את ריצת \( M \) על \( x \) למשך מספר צעדים כה גדול עד כי מובטח ש-\( M \) תעצור על \( x \), ולכן \( U \) תענה הפוך מ-\( M \). מכאן שאף מכונה פולינומית אינה מקבלת את אותה שפה בדיוק כמו \( U \), וזהו סוף הסיפור.

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

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

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

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

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

אלא מה? הוכחות רלטיביסטיות הן “עיוורות” לחיזוק שכזה. אם אנחנו מצליחים להוכיח באופן רלטיביסטי ששתי מחלקות \( A,B \) שונות זו מזו, ואנו מחזקים את המכונות בשתי המחלקות באמצעות אותו אורקל, ההוכחה ממשיכה לעבוד באותו האופן; בכל פעם שסימולציה של מכונה \( M \) מתוך \( A \) תדרוש קריאה לאורקל, \( U \) תוכל לבצע את הקריאה הזו כי גם ל-\( B \) הוספנו גישה לאותו אורקל. באופן פורמלי זה אומר שאם הוכחנו רלטיביסטית ש-\( A\ne B \) אז גם \( A^{L}\ne B^{L} \), כאשר \( A^{L} \) אומר, כצפוי, “המחלקה \( A \) כשמוסיפים למכונות בה גישה לאורקל לשפה \( L \)”.

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

מהן השפות \( L_{1},L_{2} \) המסתוריות הללו ואיך הולכת ההוכחה? מכיוון שהיא טכנית יחסית, אדחה אותה לפוסט נפרד.