אז מה זה עניין P=NP, בעצם?

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

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

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

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

טוב, נסחפתי.

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

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

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

ומאיפה האות P הגיעה בכלל? מהמילה Polynomial – פולינומי, שניתן לתיאור באמצעות פולינום. זהו שם טכני – "זמן ריצה יעיל" מזוהה עם "זמן ריצה שניתן לחסימה באמצעות פולינום" וממש לא נורא אם לא תבינו למה הכוונה כאן.

כעת ל-NP. בלבול מאוד נפוץ הוא לחשוב ש-NP פירושו "לא ב-P" (כלומר, שה-N מסמן "Not"). המשמעות האמיתית היא שוב טכנית – Nondeterminsitic Polynomial. מה קשור אי דטרמיניזם לכאן – זה כבר לדיון אחר, והסיבות הן בעיקר היסטוריות. המשמעות של NP, שהיא מה שחשוב כאן, היא זו: בעיות שקל לבדוק את פתרונן. וכאן מתאימה דוגמה – אם אומרים לי "הפירוק לגורמים של 35 הוא 5 ו-7", קל לי לבדוק זאת – אני כופל את 7 ו-5 ומקבל 35, כצפוי. עם זאת, לא ידוע כיום שום אלגוריתם יעיל לפירוק לגורמים של מספר – כך שזוהי בעיה שקל לבדוק את פתרונה, אך לא קל לפתור (ליתר דיוק – לא ידוע אם קל לפתור אותה). גם בעיית לוח הזמנים שדיברתי עליה למעלה היא כזו – אם נותנים לכם רשימה ארוכה של קורסים שיש לשבץ בכיתות ובשעות שלא יתנגשו, תחת אילוצים מסויימים, יכול להיות מאוד קשה למצוא מערכת שעות מוצלחת; אבל אם מישהו כבר מביא לכם כזו, קל לבדוק שהיא אכן מוצלחת.  כפי שאפשר להבין מכך, NP היא מחלקת בעיות גדולה יותר מאשר P; כל מה שקל לפתור, קל גם לבדוק אם הוא פתיר (למי שהטענה הזו נשמעת קצת "חשודה", אל חשש – כשמביאים הגדרות מתמטיות מדוייקות למחלקות אלו, המשפט הזה מקבל משמעות יותר מדוייקת שנכונותה ברורה למדי).

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

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

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

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

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

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

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

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

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

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

28 תגובות על הפוסט “אז מה זה עניין P=NP, בעצם?

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

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

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

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

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

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

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

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

  5. I would have to agree with Gadi. I think that Cohen's proof of the independence of the Continuum Hypothesis could serve as a good analog. The problem had a similar logical flavor, there were substantial barriers and a completely new approach was needed. And this completely new approach did appear, basically out of nowhere (more precisely, out of an entirely different field).

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

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

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

  8. 1. בתחילת הפוסט כתוב "בעיות שאינן שייכות ל-P נפתרון מדי יום ביומו בעזרת אלגוריתמים לא מושלמים, שבמקרים מסויימים עשויים לעבוד גרוע מאוד, אבל עבור המקרים הממוצעים שמגיעים אליהם הם דווקא יעילים למדי". אני אישית לא מכיר בעיות שכאלה. ליתר דיוק – המחלקה הכי "קלה" שמכילה בעיות אשר אינן שייכות ל P בוודאות היא ExpTime, ואני אשמח לשמוע על אלגוריתם פולינומיאלי הסתברותי לבעיה שהיא שלמה ב ExpTime.

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

  9. 1. זה סתם ניטפוק. הכוונה הייתה ל"בעיות שאינן ידועות כשייכות ל-P" והכוונה הייתה בפרט לבעיות NP-שלמות. יתוקן.

    2. כאמור בפוסט, יש סיבות טכניות לבחירה בפולינומים דווקא (רובסטיות של המודל וכאלה) ולכן נכון יותר לחשוב על P בתור "לא קשה באופן מבהיל". חשוב לזכור שבסיבוכיות מתעניינים יותר בשאלה "מה קשה" ולא בשאלה "מה קל", והעניין המרכזי הוא בבעיות שאפשר להוכיח שהן *אינן* ב-P, כלומר שהן כן "קשות באופן מבהיל".

    לי אישית כבר יצא לראות כמה בעיות שהשתייכו ל-P רק עם מעריך מבהיל (המעריך שלך הוא עוד שפוי יחסית; יש בעיות ששייכות ל-P עם מעריך שהוא "מגדל" שבו מספר הקומות תלוי באיזה קבוע c שיכול להיות גדול).

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

    ככלל, אני לא מכיר אף משפט בסיבוכיות ש"נופל" אם מחליפים את השימוש בפולינומים בזמני ריצה כלליים ומציינים במפורש את התלויות ביניהם.

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

  11. I stand corrected. אני שמח לראות שכן הייתה התייחסות רצינית לנושא לפחות במקום אחד.

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

  13. קצת משעשע שאתה שואל את זה כי אני מדבר על זה קצת בפוסט הבא:

    http://www.gadial.net/?p=716

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

  14. פינגבאק: אז מה זה IP=PSPACE? « לא מדויק

  15. פינגבאק: אז מה הקטע עם המשפט האחרון של פרמה? « לא מדויק

  16. פינגבאק: משפט Valiant-Vazirani, או: איך להרוג השמות מספקות עם פונקציות תמצות אקראיות « לא מ

  17. פינגבאק: משפט לדנר, או – מפרקים לגורמים את NP « לא מדויק

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

  19. דוגמת ההצפנה הוזכרה בפוסט.

    (וכפי שנאמר שם, אם P=NP זה הרבה יותר חמור מסתם פריצה של RSA, שהוא שיטת הצפנה אחת ויש לו אלטרנטיבות; אם P=NP זה אומר שהצפנת מפתח ציבורי היא פשוט בלתי אפשרית).

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

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

  22. פינגבאק: על P=NP מעל חבורות אבליות – מבוא שלם | לא מדויק

  23. פינגבאק: רזולוציה – איך אפשר להוכיח שאי אפשר? | לא מדויק

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

כתיבת תגובה

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