על בעיות שהן בכלל תסבוכת שלמה

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

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

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

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

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

אגדיר בצורה פורמלית רק רדוקציות מבעיות הכרעה לבעיות הכרעה, למרות שקיימת דרך כללית יותר לדבר על רדוקציות (בפרט, באמצעות המושג של “אורקל”, שעליו אני מקווה לדבר בעתיד). סוג הרדוקציות שאציג הזה נראה מגביל למדי, וזה אינו מקרי; המטרה היא להפיק כמה שיותר אינפורמציה ממושג הרדוקציה הזה, והגדרה רחבה יותר הייתה עשויה לפגוע בכך.

אם כן, בהינתן בעיה A ובעיה B, רדוקציה מ-B ל-A היא פונקציה \( f \) שלוקחת קלט אפשרי \( x \) לבעיה B והופכת אותו לקלט \( f(x) \) לבעיה A, כך שפתרון של A יענה “כן” על \( f(x) \) אם ורק אם פתרון של B צריך לענות “כן” על \( x \).

דוגמה קלאסית לרדוקציה היא מבעיית העצירה (האם מכונת טיורינג M מסיימת את ריצתה על קלט x נתון) אל הבעיה של בדיקה האם מכונת טיורינג M מסיימת ריצה על הקלט ה”ריק” (כלומר, בלי קלט). לכאורה, אפשר היה לחשוב שהבעיה השניה עשויה להיות קלה “ממש” מהראשונה - הרי בשניה צריך לענות רק על מקרה פרטי מאוד של הראשונה. בפועל, קיימת רדוקציה כזו: אם מקבלים קלט לבעיית העצירה, \( M,x \), בונים באמצעותו מכונה חדשה - \( M_x \), שפועלת כך על הקלט הריק: ראשית, היא כותבת את \( x \) על הסרט שלה. שנית, היא מחזירה את הראש הקורא להתחלה. שלישית, מאותו הרגע היא מתנהגת בדיוק כמו \( M \). מה עשינו? יצרנו מכונה שעוצרת על הקלט הריק אם ורק אם המכונה המקורית \( M \) עוצרת על הקלט \( x \). על כן, פתרון לבעיה השניה מבטיח שנפתור גם את בעיית העצירה; ולכן, בעיית העצירה לא קשה יותר מאשר הבעיה השנייה. מן הסתם הבעייה השנייה לא קשה יותר מבעיית העצירה, ולכן שתי הבעיות שקולות מבחינת כוחן החישובי.

צריך להיות מאוד זהירים כאן. הדרך הפשוטה ביותר להמחיש זאת היא עם ה”רדוקציה” הבאה מבעיית העצירה (הבלתי פתירה) לבעיית בדיקת הראשוניות (הפתירה מאוד): בהינתן מכונה M וקלט x, הפונקציה \( f \) תחזיר 3 אם \( M \) עוצרת על \( x \), ו-4 אחרת…. ברור שהפונקציה הזו היא חוקית, וגם ברור שהיא רדוקציה על פי ההגדרה שנתתי, ועם זאת גם ברור שבעיית העצירה קשה הרבה יותר מבעיית בדיקת הראשוניות. מה השתבש כאן?

מה שהשתבש הוא ש”החבאנו” את אי הפתירות של בעיית העצירה בתוך הרדוקציה עצמה. הרדוקציה עצמה “פותרת” את בעיית העצירה, ועל פי הפתרון מחליטה האם למפות את הקלט למספר 3 או 4. לכן, כדי שרדוקציה תהיה בעלת ערך כלשהי, היא לא צריכה להיות חזקה מדי; במקרה שלנו, היינו צריכים לדרוש שהרדוקציה תהיה פונקציה ניתנת לחישוב; זה ימנע מצב שבו בעיה בלתי ניתנת לחישוב ניתנת לרדוקציה אל בעיה הניתנת לחישוב, ולכן זה פותח פתח להוכחה שהמוני דברים בלתי ניתנים לחישוב - אם נצליח להראות רדוקציה ניתנת לחישוב מבעיית העצירה אל משהו, זה אומר שגם ה”משהו” לא פתיר.

דבר דומה קיים גם עבור המחלקה NP, רק שכאן הדרישה מהרדוקציות חריפה יותר מאשר סתם “ניתנות לחישוב” - דורשים שהן יהיו ניתנות לחישוב בזמן פולינומי. שוב, מאותן סיבות. הדבר מבטיח שאם A ניתנת להכרעה בזמן פולינומי (כלומר, שייכת ל-P) וקיימת רדוקציה פולינומית מ-B אל A, אז גם B ניתנת לחישוב בזמן פולינומי. וכאן נכנס לתמונה מושג השלמות (Completeness) בפעם הראשונה, בשאלה הבאה: האם קיימת איזו שהיא בעיה ב-NP שכל בעיה אחרת ששייכת ל-NP ניתנת לרדוקציה אליה?

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

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

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