P לעומת NP

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

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

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

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

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

במאמר שלי מ-1972 הראיתי כי שלמות-NP היא תופעה נפוצה מאוד על ידי פיתוח עץ של רדוקציות המראה ש-21 בעיות קלאסיות הן כולן שלמות-NP. התרשים שעל הלוח מדגים את הרדוקציות בין 13 מן הבעיות האלה. כל קודקוד בעץ מסומן בשמה של אחת הבעיות ב-NP, וכל קשת פירושה שאפשר להמיר את הבעיה העליונה לתחתונה באופן יעיל; לכן, אם קל לפתור את הבעיה התחתונה, הרי שקל לפתור גם את העליונה. לפיכך, אם ניתן לפתור באופן יעיל ולו אחת מן הבעיות האלה, אזי אפשר לפתור באופן יעיל גם את Sat, וממילא, בהתאם לתוצאה המכרעת של קוק, יהיה קל לפתור כל בעיית NP.

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

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