בקטנה: האם נמצאה הוכחה לכך ש-P שונה מ-NP? אולי ואולי לא, אבל בינתיים בואו נספר לכם על מה מדובר בכלל, מדוע אנשים מתרגשים מזה ולמה יש על זה פרס של מיליון דולר.
מאת גדי אלכסנדרוביץ'.
במדעי המחשב התאורטיים עוסקים בשאלות הרות גורל, כגון "מה בכלל אפשר לעשות עם מחשב?" הכוונה איננה לכך שמחשב לא יכול להתאהב (אולי הוא יכול, למה להיות פסימיים?) או לכתוב שירה (חכו עוד כמה שנים ותראו), אלא לכך שיש בעיות מתמטיות קונקרטיות מאוד שמחשב לא יכול לפתור. למשל, אין מחשב שיכול לפתור את הבעיה הבאה באופן כללי: בהינתן קוד של תוכנית מחשב, לקבוע אם היא תסיים לרוץ יום אחד (בהינתן שהיא לא תקרוס בגלל חוסר זיכרון או שהמחשב שעליה היא רצה מתפוצץ וכדומה), או תמשיך לרוץ לעד. הבעיה הזו נקראת "בעיית העצירה", ואנחנו יודעים כבר משנות ה-30 שאי אפשר לפתור אותה בעזרת מחשב, בזכות המתמטיקאי אלן טיורינג ואחרים.
בשנים שעברו מאז תקופתו של טיורינג הגיעו מדעני המחשב למסקנה שגם בתאוריה, לא תמיד נכון להתעלם מהזמן או מכמות הזיכרון שתוכנית מחשב דורשת. כך נולדה תורת הסיבוכיות: התורה המתמטית שעוסקת בשאלה, מהו הקושי החישובי של בעיות? משאב הסיבוכיות המרכזי שמדברים עליו במסגרת התורה הוא זמן חישוב. מכיוון שאותה תוכנית מחשב רצה במשך זמן שונה על מחשבים שונים, לא מודדים זמן חישוב באופן "אבסולוטי", בשניות, אלא מסתפקים בהערכות של מספר הצעדים שתוכנית המחשב מבצעת.
בואו ניקח דוגמה פשוטה: תוכנית מחשב שמקבלת שני מספרים ומתבקשת לכפול אותם ולהחזיר את התוצאה. המספרים הם הקלט של התוכנית והתוצאה היא הפלט שלה. ברור שככל שהמספרים גדולים יותר, כך זמן החישוב רב יותר: קל יותר לכפול מספרים דו ספרתיים מאשר מספרים עם 1,000 ספרות כל אחד. לכן נוהגים למדוד את מספר צעדי החישוב ביחס לגודל הקלט, ואומרים דברים, כגון "זמן החישוב הוא בערך פי 3 מגודל הקלט", או "זמן החישוב הוא בערך גודל הקלט בחזקת 2", או "זמן החישוב הוא בערך גודל הקלט בחזקת 100". בכל המקרים הללו זמן החישוב נחשב ל"לא כל כך נורא", כי הגדלה של הקלט פי 2 לא מגדילה את זמן החישוב בצורה מטורפת. לזמן חישוב שכזה, של "גודל הקלט בחזקת מספר קבוע כלשהו", קוראים זמן חישוב פולינומי.
מה כן נחשב לזמן חישוב נורא? למשל, מה שמכונה זמן חישוב אקספוננציאלי, זמן חישוב שבו לא מעלים את גודל הקלט בחזקה כלשהי, אלא גודל הקלט עצמו הוא החזקה. כאן כל גידול בגודל הקלט מקפיץ את זמן החישוב בצורה אסטרונומית. למשל, אם זמן החישוב הוא 2 בחזקת גודל הקלט, אז כל הגדלה של הקלט, אפילו ב-1, תגרום לזמן החישוב הכולל לקפוץ פי 2. אם גודל הקלט הוא 1,000, אז 2 בחזקת 1,000 הוא כבר מספר עצום בהרבה ממספר המילי-שניות שחלפו מאז תחילת היקום, 4.35 כפול 10 בחזקת 20!
כדי לפשט לעצמם את העניינים, מדעני המחשב מתמקדים בשיח על בעיות חישוביות שהתשובה להן היא "כן/לא". בעיות כאלו נקראות בעיות הכרעה. לדוגמה: נתון לוח סודוקו חצי פתור. האם יש לו פתרון מלא? זוהי שאלת כן/לא. (שאלה מעניינת יותר היא "מהו הפתרון?!" אבל אפשר להראות שאם יש לנו יכולת לפתור את בעיית ההכרעה אז לא קשה גם למצוא את הפתרון.)
כעת ניתן להסביר מהי P. זהו השם שמדעני המחשב נותנים לכל אוסף בעיות ההכרעה שאפשר לפתור בזמן "סביר", פולינומי. מה שמחוץ למחלקה הזו נחשב לקשה מדי לפתרון באופן כללי, אם כי בפועל יש אלגוריתמים שפותרים גם בעיות שאינן ב-P ועובדים באופן סביר בחלק מהמקרים. השם P מגיע מהמילה Polynomial, "פולינומי" (זמן פולינומי).
אם כן, מהי NP? זהו אוסף של בעיות הכרעה שמקיימות תכונה "נחמדה" אחרת: גם אם לא בטוח שאפשר לפתור אותן בזמן פולינומי, אפשר לבדוק אם הן פתירות על ידי התבוננות בפתרונות המוצעים עבורן. ניקח לדוגמה שוב את בעיית הסודוקו שלנו: אולי קשה למצוא פתרון ללוח סודוקו, אבל אם מישהו כבר טרח ומצא פתרון והוא נותן לכם אותו, קל יחסית לבדוק שהפתרון נכון (פשוט בודקים כל שורה, עמודה וריבוע מתאימים). אם כן, בעיות NP הן עדיין קלות במידה מסוימת, אף ש אינן ב-P. שימו לב לכך שכל בעיה ב-P שייכת גם ל-NP: אם קל לבדוק שבעיה היא פתירה, עם או בלי פתרון (שייכות ל-P) אז בוודאי קל לבדוק אם היא פתירה כשנותנים לכם פתרון (שייכות ל-NP). השם NP פירושו "Nondeterministic Polynomial", ובעברית, "בעיות שניתנות לפתרון אי-דטרמיניסטי בזמן פולינומי". (נעזוב הפעם את ה"לא-דטרמיניסטי", זה משהו ששקול מתמטית לניסוח "בדיקת הפתרונות" שראינו.) הפירוש אינו "Non-polynomial" ("לא פולינומי") כפי שחושבים בטעות לפעמים.
את NP הגדירו בשנות ה-70, ומאז התברר שעשרות אלפי בעיות במדעי המחשב שייכים אליה. לא תהיה זו הגזמה לומר שמרבית הבעיות המעניינות במדעי המחשב שאיננו יודעים אם הן ב-P, שייכים ל-NP. על כן זו שאלה מעניינת ביותר, האם P=NP? כלומר, האם כל בעיה שקל לבדוק אם היא פתירה בהינתן פתרון, היא גם פתירה בלי שיתנו לנו את הפתרון? או בלשון ציורית - האם לפתור שיעורי בית זה קל כמו לבדוק אותם?
אם יוכיחו ש-P=NP ההשלכות של זה עשויות להיות אדירות. למשל, הצפנות כמו RSA ייקלעו לצרה צרורה, כי ינבע מ-P=NP שאם אפשר לבדוק אם מישהו אחר הצליח לפצח אותן, אז גם אפשר לפצח אותן עצמאית. העניין הוא שמעטים הם מדעני המחשב שחושבים ש-P=NP - זה פשוט יותר מדי. זו גם תוצאה מוזרה מבחינה פילוסופית, הרי לפתור שיעורי בית זה קשה בהרבה מלבדוק אותם! נכון? מבחינה פרקטית, כבר בשנות ה-70 הוכיחו כי יש עשרות אלפי בעיות ב-NP, שאם פותרים ולו אחת מהן בזמן פולינומי, אז נובע מכך ש-P=NP (בעיות כאלו נקראות "NP-שלמות"). הבעיות הללו צצו בתחומים רבים ושונים במדעי המחשב, וניסו (ועדיין מנסים) למצוא עבורן פתרונות יעילים ככל האפשר. אם אחת מהן הייתה ב-P, סביר להניח שכבר היו מגלים זאת. האינטואיציה הזו מובילה את רוב מדעני המחשב להניח ש-P שונה מ-NP, ולכן שכל הבעיות ה-NP-שלמות אינן ניתנות לפתרון בזמן פולינומי.
אם כן, מדוע לא מוכיחים ש-P שונה מ-NP? התשובה היא שניסו. ניסו בשלל דרכים יצירתיות, והכול נכשל. נכשל בצורה מפוארת. אם מנסים, למשל, להשתמש בשיטה שבה אלן טיורינג הוכיח שבעיית העצירה אינה ניתנת לפתרון כלל, אז ניסיון השימוש הזה נכשל לחלוטין; אפשר לתת הוכחה לכך ששיטות כמו של טיורינג לא יכולות לעבוד על בעיית P=NP. כבר למעלה מ-40 שנים, מאז שהבעיה הזו נוסחה במפורש, והיא ממשיכה לחמוק מאיתנו. "תחושת הבטן" של אנשי מדעי המחשב היא שכדי להתמודד עם הבעיה ולהוכיח ש-P שונה מ-NP יש צורך בגישה מתמטית חדשה לגמרי לתורת הסיבוכיות, בדומה לאופן שבו כדי להוכיח את המשפט האחרון של פרמה בן המאה ה-17 נזקקו המתמטיקאים בסופו של דבר למתמטיקה המאוד מתוחכמת של המאה ה-20 ולשלל מושגים שלא היו קיימים כלל בזמנו של פרמה. פתרון "פשוט" לבעיית P=NP, שלא יכלול מתמטיקה חדשה שכזו, יהיה סנסציה לא פחות מהוכחה ש-P=NP.
מכיוון שזו בעיה כל כך מעניינת, בשנת 2000 כלל אותה מכון קליי למתמטיקה ב"שבע בעיות המילניום" שלו, שפתרון כל אחת מהן מזכה בפרס של מיליון דולר. רוצים להצטרף לאתגר או שהפחדנו אתכם מספיק?
 
לקריאה נוספת:
https://goo.gl/HuXEku
https://goo.gl/UfNPm6