שאלת P=NP.
במדעי המחשב מסומנת ב-P מחלקת כל הבעיות הניתנות לפתרון דטרמיניסטי בזמן ריצה פולינומי. זוהי המחלקה המזוהה ביותר עם בעיות שניתנות לפתרון בפועל (אף כי זיהוי זה אינו מדויק). ידוע כי NP מכילה כל בעיה השייכת ל-P: אם בעיה שייכת ל-P אז ניתן לדעת אם פתרונה הוא 'כן' או 'לא' על ידי חישוב יעיל, אפילו ללא צורך בהוכחה (ולחלופין, כל מכונה דטרמיניסטית הפותרת בעיה יכולה תמיד להיחשב כמכונה אי-דטרמיניסטית "מנוונת" שאינה משתמשת באי-דטרמיניזם שלה). השאלה המהותית היא אם הכלה זו היא הכלה ממש, כלומר, אם קיימות בעיות ב-NP שאינן ניתנות לפתרון יעיל, או שמא כל בעיה ב-NP ניתנת גם לפתרון יעיל.
בניסוח שקול, "האם P=NP" היא השאלה אם זיהוי יעיל של פתרון גורר מציאה יעילה של פתרון. כלומר, בהינתן בעיה שאנו מחפשים לה פתרון מסוים, האם היכולת לזהות ביעילות שמצאנו פתרון נכון גוררת גם שאנחנו מסוגלים למצוא פתרון שכזה ביעילות (הוכחת השקילות אינה מיידית)?
שאלה זו אינה בעלת ערך אקדמי בלבד. עם התפתחות השימושים המסחריים של הקריפטוגרפיה בעידן המחשב, ובמיוחד במסחר אלקטרוני, הפכה התשובה לשאלה לבעלת חשיבות כלכלית לא מבוטלת. הסיבה לכך היא שרוב המסחר האלקטרוני ותעשיית האבטחה הדיגיטלית מסתמכים על אלגוריתמים שיכולת ההצפנה שלהם נובעת מחוסר היכולת הנוכחי לפתור בעיות NP בזמן סביר. דוגמה נפוצה היא אלגוריתם ההצפנה RSA, שמבוסס על כך שלא ידוע פתרון פולינומי לפירוק לגורמים של מכפלת שני מספרים ראשוניים, ולכן פירוק שכזה דורש זמן רב מאוד כאשר המספרים הראשוניים שנבחרו הם גדולים מספיק. עם זאת, אף אם P אינו שווה ל-NP, עדיין ייתכן פירוק מהיר לגורמים.
למעשה, אם יוכח ש-P=NP הדבר ינחית מכה קשה מאוד על הקריפטוגרפיה כולה. למשל, הדבר יראה כי לא קיימות פונקציות חד-כיווניות, כלומר הצפנת מפתח ציבורי אינה אפשרית שכן קל לזהות שכתב גלוי הוצפן לכתב סתר נתון באמצעות מפתח ציבורי (פשוט מצפינים את הכתב הגלוי בעזרת המפתח ומשווים לכתב הסתר), ומכאן שאם זיהוי יעיל גורר חיפוש יעיל, הרי שבהינתן הודעה מוצפנת והמפתח הציבורי שהצפין אותה, ניתן יהיה למצוא ביעילות את הכתב הגלוי המקורי. השלכה נוספת של הוכחת השוויון P=NP תהיה הוכחת אי קיומם של מחוללים פסאודו-אקראיים אמיתיים (דהיינו, הדבר יראה שהמחוללים שנמצאים כיום בשימוש אינם מקיימים את מלוא התכונות הנדרשות מהם, ושלא יכולים להתקיים מחוללים שכן מקיימים תכונות אלו).
תחום נוסף שהוכחת השוויון P=NP יכולה להשפיע עליו (לטובה) באופן קיצוני, הוא התחום העוסק באלגוריתמי קירוב. אם יוכח ש-P=NP, התחום יהפוך למיותר לכאורה, שכן אם ניתן לפתור כל בעיה (מאלו שבהן התחום עוסק) באופן מדויק, אין צורך בקירובים. אם כי עדיין יהיה לתחום שימוש מעשי שכן לעיתים קל יותר לגלות אלגוריתמי קירוב.
הדים לשאלה זו ניתן למצוא כבר במכתב ששלח קורט גדל לג'ון פון נוימן בשנת 1956, ומאז שנוסחה פורמלית בשנות השבעים היא בעיה פתוחה מרכזית במדעי המחשב, ואחת מ"שבע בעיות המילניום" של מכון קליי למתמטיקה. כל מאמציהם של החוקרים לפתור בעיה זאת עלו בתוהו, והסברה הרווחת בקרב מדעני מחשב העוסקים בבעיה כיום היא כי P≠NP, אך יהיה צורך בגישה חדשה לגמרי כדי לתקוף את הבעיה. עם זאת, כמה ממדעני המחשב המובילים, כגון דונלד קנות', נוטים להאמין כי P=NP. בדומה לבעיות פתוחות מפורסמות אחרות, קיימים רבים הטוענים כי הצליחו להוכיח או להפריך את הטענה (או אף הראו שלא ניתן להכריע אותה באמצעות שיטות ההוכחה המקובלות), אך טענות אלו אינן עומדות בביקורת עמיתים ולא התקבלו על הקהילה המדעית.
בעיות NP-קשות (NP-Hard) ובעיות NP-שלמות (NPC).
מכיוון שקשה לאמוד את הסיבוכיות החישובית האבסולוטית של בעיות הכרעה, כלומר לאמוד את כמות המשאבים הנדרשת לפתרונה (קושי שמתבטא, למשל, בכך שהשאלה האם P=NP עודנה פתוחה), נהוג במדעי המחשב לאמוד סיבוכיות של בעיות באופן יחסי האחת לשנייה. בעיה A היא בת-חישוב "לפחות כמו" הבעיה B, אם בהינתן פתרון ל-B ניתן להשתמש בו כדי לבנות פתרון עבור A. המושג הפורמלי שמתאר תכונה זו הוא רדוקציה חישובית. באופן דומה A היא בת-חישוב יעיל "לפחות כמו" הבעיה B אם בהינתן פתרון יעיל ל-B ניתן להשתמש בו לבניית פתרון יעיל ל-A - במקרה זה הרדוקציה מ-B ל-A צריכה להיות רדוקציה פולינומית.
על בסיס הגדרה זו בעיית הכרעה מכונה NP-קשה אם היא בת-פתרון מבחינה חישובית לפחות כמו כל בעיה השייכת ל-NP. כלומר, בעיה A תקרא NP-קשה אם ורק אם לכל בעיה B ב-NP קיימת רדוקציה פולינומית מ-B ל-A. פתרון יעיל לבעיה NP-קשה כלשהי יגרור שכל בעיה השייכת ל-NP ניתנת לפתרון יעיל, ולכן בפרט P=NP.
מבין הבעיות ה-NP-קשות, החשובות ביותר הן אלו אשר שייכות בעצמן למחלקה NP. בעיות אלו מכונות NP-שלמות. בשל תכונת הקושי שלהן, השאלה אם P=NP קמה ונופלת על כל אחת מבעיות אלו - אם עבור בעיה NP-שלמה אחת ניתן יהיה להוכיח כי היא ב-P, אז P=NP; ולחלופין, אם יהיה ניתן להראות עבור בעיה NP-שלמה אחת כי היא אינה שייכת ל-P הדבר יגרור כי P≠NP.
אין זה מובן מאליו שבעיות NP-שלמות קיימות כלל; הדבר הוכח בשנת 1971 בידי סטיבן קוק, שגם הגדיר את מחלקת הבעיות ה-NP-שלמות (אך לא השתמש בשם זה, שניתן בידי ג'ון הופקרופט בשנת 1972) והראה כי בעיית הספיקות של נוסחאות מצורת CNF ("בעיית SAT") היא NP-שלמה. הוכחה דומה ניתנה באופן בלתי תלוי בברית המועצות בידי ליאונרד לוין, ותוצאה זו נקראת כיום משפט קוק-לוין. ההוכחה כי SAT היא NP-שלמה היא ישירה - בהינתן בעיה כלשהי ב-NP, מראים כיצד ניתן לבנות רדוקציה ממנה אל SAT (כלומר, לבנות נוסחה שמתארת, במובן מסוים, את הבעיה). לאחר שהוכח כי SAT היא NP-שלמה נסללה הדרך להראות עבור בעיות רבות נוספות כי הן NP-שלמות, שכן כדי להראות כי בעיה ב-NP היא NP-שלמה די להראות רדוקציה מבעיה NP-שלמה ידועה אליה.
רשימת 21 הבעיות ה-NP-שלמות של קארפ.
את הכפפה הרים בשנת 1972 ריצ'רד קארפ שהראה במאמרו עבור 21 בעיות חשובות אחרות במדעי המחשב כי הן NP-שלמות (בהתבסס על כך ש-SAT היא NP-שלמה). מאמר זה הצביע על כך שיש טעם בהגדרת מחלקת סיבוכיות חדשה, NPC, של אוסף הבעיות ה-NP-שלמות. מאז הוכח כי NPC מכילה אלפי בעיות ידועות, מכל תחומי מדעי המחשב.
להלן הבעיות שתיאר קארפ במאמרו, ומהוות דוגמאות "קלאסיות" לבעיות NP-שלמות:
כפי שצוין, ניתן להוכיח שעוד אלפי בעיות אחרות הן NP-שלמות, על ידי רדוקציה פולינומית מבעיה אחרת שהוכחה כ־NP-שלמה.
בעיות NP-קשות שאינן NP-שלמות.
אף שעיקר העניין בחקר בעיות NP-קשות מתמקד בבעיות ה-NP-שלמות (שמכל הבעיות ה-NP-קשות הן הבעיות ש"סביר ביותר" שיהיו ניתנות לפתרון בזמן יעיל) קיימות גם בעיות NP-קשות שאינן NP-שלמות. הדוגמה המובהקת והפשוטה ביותר היא של בעיית העצירה - בהינתן תוכנית (או אלגוריתם) וקלט עבורה, האם היא תעצור?
בעיה זו ידועה כבעיה שכלל לא ניתנת לחישוב. עם זאת, ניתן לבצע אליה רדוקציה פולינומית מכל בעיה השייכת ל-NP באופן פשוט - בהינתן אלגוריתם formula_50 שפותר (גם אם לא ביעילות) את הבעיה שב-NP, ניתן לשנותו ולקבל אלגוריתם חדש formula_51 כך שאם אין לבעיה פתרון, formula_51 ייכנס ללולאה אינסופית (שינוי שכזה קל לבצע בזמן פולינומי, כך שהרדוקציה היא פולינומית). כעת, בהינתן קלט formula_5 לבעיה המקורית, הרדוקציה מחזירה את הצמד formula_54.
קשרים עם מחלקות סיבוכיות דומות.
המחלקה co-NP.
הגדרתה של NP היא בלתי-סימטרית במהותה: שפה שייכת ל-NP אם לכל מילה השייכת לשפה קיימת "הוכחה" לשייכות זו שניתן לבדוק ביעילות; לעומת זאת, לא נדרש מאום ממילים שאינן שייכות לשפה (פרט לכך שהבודק לא יקבל גם אותן בטעות). ניתן להגדיר מחלקת סיבוכיות מקבילה, בה מתהפכות היוצרות: אם מילה אינה שייכת לשפה קיימת לכך "הוכחה" שמאפשרת לבודק להשתכנע בכך שהמילה אינה בשפה ולדחות אותה (אם כי על "הוכחות" אחרות הוא עשוי לקבל), בעוד שנדרש ממנו לקבל כל מילה שכן שייכת לשפה. דוגמה לשפה שכזו היא שפת הראשוניים שהוזכרה לעיל: בהינתן מספר שאינו ראשוני, "הוכחה" לכך תהיה פשוט מחלק לא טריוויאלי שלו. מחלקת השפות שניתן לבדוק ביעילות "הוכחות" לאי שייכות מילה אליהן מכונה co-NP. פורמלית, ניתן להגדיר אותה כאוסף כל השפות formula_9 כך שמשלימתן formula_56 שייכת ל-NP.
לא ידוע אם NP=co-NP. טענה זו חזקה פחות מהטענה כי P=NP; אם P=NP אז נובע מכך מיד כי NP=co-NP=P (שכן P סגורה למשלים) אך ייתכן כי NP=co-NP ועם זאת עדיין formula_57. מצד שני, הוכחה כי formula_58 תגרור מיידית כי גם P שונה מ-NP. ההנחה הרווחת בקרב מדעני המחשב היא כי השוויון אינו מתקיים, והדבר נותן מעמד מיוחד לבעיות השייכות הן ל-NP והן ל-co-NP; אלו בעיות שלא סביר כי הן NP-שלמות שכן הדבר יגרור כי NP=co-NP. הבעיה המפורסמת ביותר השייכת גם ל-NP וגם ל-co-NP היא בעיית הפירוק לגורמים, ותכונה זו שלה הופכת אותה למועמדת הטבעית ביותר לבעיה שמחד אינה שייכת ל-P, (כפי שמקובל להאמין היום) ומאידך אינה NP-שלמה (משפט לדנר מראה קיום של שפה כזו, בהנחה ש-P שונה מ-NP, אך ההוכחה היא בלכסון ואינה מתארת שפה שצצה באופן "טבעי").
קן ווטנאבי
ערבה בוכייה
ערבה בוכיה
מכללה לביטחון לאומי
אווטאר (סרט)