מה אפשר ואי אפשר לחשב?

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

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

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

חמש שאלות גדולות שלמדע אין עדיין תשובה עליהן | לפרויקט המלא

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

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

פרופ' דוד הראל
פרופ' דוד הראלצילום: תומר אפלבאום

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

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

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

נניח למשל שיש רשימה של n שמות ומספרי טלפון, ואנו רוצים לעשות עליה פעולת חישוב כלשהי, כמו למיין אותה בסדר אלפביתי כדי להכין ממנה ספר טלפונים. "אם נמצא אלגוריתם שזמן החישוב שלו יהיה לא יותר מ-n כפול שתיים, n כפול 100, n בריבוע או אפילו n בחזקת 10, כל אלה הם פולינומים, וזמן החישוב יהיה סביר", מסביר פרופ' הראל. ואולם, אם זמן הפעולה יהיה 2 בחזקת n, מדובר בחריגה מתחום החישוב הפולינומיאלי אל החישוב המעריכי - שכבר אינו סביר כלל. כך לדוגמה, 50 בריבוע הם רק 2,500, בעוד ש-2 בחזקת 50 הם 1,125,899,906,842,624.

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

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

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

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

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

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

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

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

תגובות

הזינו שם שיוצג באתר
משלוח תגובה מהווה הסכמה לתנאי השימוש של אתר הארץ