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


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



על מוגבלותן של מכונות חישוב
מחבר: נעם ליבנה


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

דמיינו לעצמכם שאתם סוכני מכירות עצמאיים, והחלטתם לבקר בעשר בירות באירופה, לשווק את מרכולתכם. אתם מתיישבים מול סוכן הנסיעות, ובפניכם שאלה חשובה: באיזה סדר תבקרו בבירות? לכל טיסה מיעד א' ליעד ב' יש מחיר. השאלה היא: באיזה סדר נעבור בעשר הבירות כך שהמחיר יהיה מינימלי? ההבדל בין מסלול למסלול עלול להתבטא באלפי דולרים, שאינכם רוצים לבזבז לשווא. תשובה נאיבית יכולה להיות: "נעבור על כל האפשרויות, ונבחר את הזולה ביותר". כמה אפשרויות כאלה יש? התשובה היא !10 (עצרת של 10), כלומר 3,628,800 אפשרויות. ברור שזה לא פרקטי לעבור על כולן. אם כן, נראה שהייתם בוחרים בסדר כלשהו, ויוצאים בהרגשת החמצה שלו היתה בידיכם פיסת מידע קטנה (מהו הסדר האופטימלי לעבור בערים), ייתכן שהייתם עשירים יותר בכמה מאות או אלפי דולרים עכשיו. אז מה עושים? היינו רוצים אלגוריתם שיסביר לנו איך בקבלנו רשימת ערים כזאת, עם רשימת מחירי טיסה בין כל שתי ערים, נחשב "בזמן סביר" מהו המסלול האופטימלי מבחינת המחיר עבור אותה רשימה (בהמשך נגדיר בצורה קצת יותר מדויקת מהו "אלגוריתם" ולמה אנו מתכוונים באומרנו "זמן סביר").

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

מהו אלגוריתם?

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

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


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

איך עובד כאן האלגוריתם? ראשית, ברצוננו להגיע לסוף המספר, בכדי לגלות אם רשום שם 0 או 1 (השרטוט למטה מתאר את פעולת המכונה). ידוע לנו שהמכונה מתחילה תמיד ממצב א'. לכן במצב זה, אם קראנו 0 או 1, נשאיר על הסרט אותה אות, נזוז ימינה משבצת אחת, ונשאר במצב א' (שורות 1,2 בטבלה). נמשיך לנוע ככה לאורך המספר, עד שקראנו רווח (שורה 3 בטבלה). כעת, אנו יודעים שאנו נמצאים משבצת אחת מימין לספרה האחרונה. לכן נזוז שמאלה, ונעבור למצב חדש, מצב ב', שהוא המצב שבודק את הספרה האחרונה. אם קראנו 0 (שורה 4), נזוז ימינה, ונעבור למצב ג', שתפקידו לכתוב "0", ולסיים, ואם קראנו 1 (שורה 5), נזוז ימינה, ונעבור למצב ד', שתפקידו לכתוב "1" ולסיים. ייתכן שהתיאור נראה לכם מעט מסורבל, אך ברור שלאחר שמבינים את העיקרון ניתן לדבר ביתר כלליות על מכונות טיורינג ללא ירידה כה מפורטת לפרטים. חשוב לציין, יחד עם זאת, שמודל פשוט זה ניתן לתיאור בצורה פורמאלית, ושבמודל זה ניתן לחשב כל פונקציה שמחשב מחשב-העל המשוכלל ביותר שקיים היום בעולם. אם כן, מעתה, כשנרצה לדבר על אלגוריתם, נדבר בעצם על מכונת טיורינג, כשעתה ביכולתנו לנסח טענות פורמאליות על האלגוריתם, ולהוכיח אותן.

מספר
שורה
"לפני" "אחרי"
מצב המכונה אות שהראש קורא אות שהראש כותב לאן להזיז את הראש לאיזה מצב לעבור
1 א(התחלה) 0 0 ימינה א
2 א (התחלה) 1 1

ימינה

א
3 א (התחלה) רווח רווח שמאלה ב
4 ב 0 0

ימינה

ג
5 ב 1 1

ימינה

ד
6 ג רווח 0

ימינה

סיום
7 ד רווח 1

ימינה

סיום

פעולת מכונת טיורינג הבודקת זוגיות של מספרבינארי

איך מודדים זמן ריצה?

כל מחשב עובד בקצב אחר, ובכל שפת תכנות אלגוריתם יכול לרוץ בקצב שונה. שוב, נרצה לדבר על מושג אחיד, ללא תלות בכל אותם גורמים טכניים, ולהעביר את הדיון לתחום המתמטי. נפנה תחילה לדוגמה קטנה. נניח שאנו בוחרים לכתוב אלגוריתם "נאיבי" לבעיית הסוכן הנוסע מלמעלה, כזה שעובר על כל האפשרויות, עבור כל אפשרות סוכם את מחירי הטיסה, ומוצא את המסלול בעל המחיר המינימאלי. כאמור, אלגוריתם כזה יאלץ לעבור, עבור n ערים, על n ! (n עצרת) אפשרויות, כלומר
2x1 ... x(n-2) x (1-n) nx אפשרויות. נניח שברשותנו מחשב אדיר שמסוגל לחשב, עבור 1000 = n, את הבעיה בשעה אחת (תרחיש מופרך ובלתי סביר בשום קנה מידה). כמה זמן ייקח למחשב לחשב את הבעיה עבור 1001 ערים? עצרת של 1001 גדולה פי 1001 מעצרת של 1000, ולכן ייקח למחשב לפחות 1001 שעות. עבור 1002 ערים כבר ייקח לו יותר ממיליון שעות, וכן הלאה. מה שאנו רואים כאן, הוא שהבעיה היא לא מהירותו של המחשב, אלא קצב גידול הפונקציה שמבטאת את זמן החישוב מול גודל הקלט. במקרה שלנו הפונקציה היא בקירוב פונקצית העצרת, פונקציה שגדלה בקצב חד מאוד ("בקירוב" - מפני שלא נכנסנו כאן לדיון על גודל הקלט. במקרה של 1000 ערים יש צורך לתאר בקלט לאלגוריתם את מרחקי הטיסה בין כל זוג ערים, כך שהקלט אינו פרופורציוני למספר הערים. אך אנו נתעלם מהפרט הזה, שאינו מהותי לדיוננו כאן).

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

זמן ריצה "פולינומיאלי" הוא כזה בו מספר הצעדים הוא מספר כלשהו, כפול אורך הקלט בחזקת מספר מסוים. לדוגמה, נניח שאנו מחפשים אלגוריתם שמקבל קבוצת מספרים וצריך להחזיר "1" אם יש שני מספרים מהקבוצה שסכומם הוא 1000 ו-"0" אם לא. האלגוריתם יכול לעבור על כל זוגות המספרים, ועבור כל זוג לסכום אותו ולבדוק אם התוצאה היא 1000. כמה זוגות כאלה יש? אם, לדוגמה, יש 200 מספרים בקבוצה, התשובה היא 2/(199x200) כלומר בערך חצי כפול 200 בריבוע. עבור כל זוג מספרים, נניח שמספר הצעדים לצורך סכימתם הוא 50. נקבל לכן שזמן הריצה של אלגוריתם כזה הוא בערך 25 כפול 200 בריבוע, כלומר מספר קבוע (25), כפול אורך הקלט בחזקת מספר מסוים (במקרה הזה 2), ולכן זהו זמן ריצה פולינומיאלי.

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


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

הקבוצה P והקבוצה NP

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

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

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

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

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

על רדוקציות, קופסאות שחורות וחכמים סיניים

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

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

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


רדוקציה פולינומיאלית

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

עדים ואימות עדים

תכונה מעניינת של שתי הבעיות שכבר בחנו היא שעל אף הקושי הגדול לפתור אותן, אם היה לנו מעין אוראקל שיודע לפתור אותן בקלות, הוא היה יכול גם לשכנע אותנו בקלות בנכונות הפתרון. נניח שאותו אוראקל היה אומר לנו "אכן יש מסלול מעגלי שעובר דרך 10 הערים, שמחירו פחות מ-$5000". היינו משיבים לו "תוכיח!", ובתגובה הוא היה פשוט מראה לנו את סדר הטיסות שעבורו מתקבל המחיר הנמוך. כל שהיה נותר לנו לעשות הוא לסכום את מחירי הטיסות הנ"ל, ולהשתכנע בצדקתו. לסדר הערים שקיבלנו מהאוראקל אנו קוראים "עֵד אימות", או בקיצור "עֵד" כי הוא מהווה עדות לכך שהתשובה עבור הקלט הנ"ל היא "כן". לאלגוריתם שמקבל קלט לבעיה ועֵד עבור הקלט, ובודק שאכן זהו עד לכך שהתשובה על הקלט הנ"ל היא "כן" (במקרה שלנו סוכֵם את מחירי הטיסה ובודק האם הסכום אכן קטן מהסכום הרצוי), אנו קוראים "אלגוריתם אימות". נשים לב שאי-אפשר "לעבוד" על אלגוריתם האימות: עבור כל קלט שהתשובה עליו היא "לא", אין שום עֵד שנוכל להצמיד אליו, כך שאלגוריתם האימות יחזיר "כן". לדוגמה, נניח שקיבלנו טבלה, בה המסלול המעגלי הזול ביותר עולה $6000, והמחיר הרצוי הוא $5000. אם ניצור עֵד כלשהו, כלומר נבחר סדר ערים, ונשלח את הקלט (הטבלה יחד עם המחיר הרצוי) ואת העֵד (סדר כלשהו של הערים), האלגוריתם יסכום את מחירי הטיסות תוך שימוש בטבלה, יגלה שהמחיר גבוה מ- $5000 ולכן יחזיר "לא". אם, לעומת זאת, יש מסלול שמחירו קטן מ- $5000, הרי שהתשובה עבור הקלט היא "כן". במקרה זה, אם נשלח למכונת האימות את הקלט, יחד עם העד (כלומר הסדר המתאים), היא תחזיר "כן".

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

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

משפט קוק-לוין

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

נאפה פשטידה רק ביום בו יתקיימו שלושת התנאים הבאים:

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

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

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

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

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

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

על השלכותיו מרחיקות הלכת של המשפט

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

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

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

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

אז מה עושים?

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

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

ביבליוגרפיה:
כותר: על מוגבלותן של מכונות חישוב
מחבר: ליבנה, נעם
תאריך: ספטמבר 2005 , גליון 85
שם כתב העת: גליליאו : כתב עת למדע ומחשבה
הוצאה לאור: SBC לבית מוטו תקשורת ולאתר IFEEL
הערות לפריט זה:

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


הספרייה הוירטואלית מטח - המרכז לטכנולוגיה חינוכית