אלגוריתם לאושר

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

 

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

 

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

 

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

 

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

 

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

 

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