אמנות הפשרה

 

 

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

 

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

 

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

 

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

 

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

 

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

 

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

 

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

 

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

 

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

 

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