הוכחה ש-P שונה מ-NP?

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

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

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

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

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

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

18 תגובות על הפוסט “הוכחה ש-P שונה מ-NP?

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

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

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

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

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

    אז לא, אני לא חושב שפרמה קל בכמה סדרי גודל מ-P=NP. לפחות טרם ראיתי נימוק משכנע לכך.

  3. כאמור, זו הייתה גרסה "לא רשמית" שכזו. ייתכן שהוא פרסם בינתיים גרסה רשמית יותר.

  4. סקוט אהרונסון לא מסכים איתך בקשר לחשיבות העניין:
    "If P≠NP is proved, then to whatever extent theoretical computer science continues to exist at all, it will have a very different character."

  5. אני חושב שאתה מוציא כאן את דבריו מהקשרם באופן פרוע. הציטוט המלא:

    "P≠NP is exactly the ‘expected’ answer! But proving that expected answer has been the central goal of the field for 40 years—not so much (in my opinion) because the answer itself is in serious doubt, as because of how much will need to be learned about computation on the way to the proof. If P≠NP is proved, then to whatever extent theoretical computer science continues to exist at all, it will have a very different character."

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

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

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

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

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

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

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

  8. גדי, ההקשר אמנם חשוב, אבל "to whatever extent theoretical computer science continues to exist at all" היא אמירה חזקה בכל הקשר (דמיין הדגשה על ה at all).

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

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

    http://rjlipton.wordpress.com/2010/08/10/update-on-deolalikars-proof-that-p%E2%89%A0np/#comment-4885

  10. מה אומר הטקסט בראש העמוד הראשון של ההוכחה בקישור???
    האם זה בשפת העלפים של טולקין???

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

  11. כמובן שאתה צודק.
    אני והשטויות שלי.
    אבל להגנתי ייאמר שיש דמיון בין הפונטים.

  12. פינגבאק: אז מה זה עניין P=NP, בעצם? « לא מדויק

  13. פינגבאק: פרוייקט "תוצאות מפתיעות בסיבוכיות" יוצא לדרך! « לא מדויק

כתיבת תגובה

האימייל לא יוצג באתר.