NP (מחלקת סיבוכיות)

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

מבוא בלתי פורמלי

בעיות רבות במדעי המחשב ניתנות לניסוח באמצעות שאלות כן/לא - האם אובייקט מסוים מקיים תכונה כלשהי. לדוגמה, בהינתן אוסף של ערים שחלקן מחוברות בכבישים ניתן לשאול אם קיים מסלול המבקר בכל הערים ועובר בכל עיר בדיוק פעם אחת (בניסוח פורמלי זוהי השאלה אם בגרף נתון קיים מסלול המילטוני). דוגמה נוספת היא בעיית החלוקה (Partition): בהינתן קבוצה של מספרים שלמים, ניתן לשאול אם ניתן לחלק את קבוצת הקלט לשתי קבוצות של מספרים כך שסכומן זהה. כך למשל, הקבוצה {1, 3, 4, 5, 8, 11} ניתנת לחלוקה לשתי קבוצות: הקבוצה {11, 5} והקבוצה {1, 3, 4, 8}, שסכום כל אחת מהן הוא 16. מאידך, הקבוצה {1, 3, 5, 6} אינה ניתנת לחלוקה כזו.
המשותף לשתי הבעיות דלעיל ולבעיות רבות נוספות הוא שאם מוצע פתרון כלשהו לבעיה (מסלול כלשהו במקרה של הדוגמה הראשונה, וחלוקה כלשהי במקרה של הדוגמה השנייה) אימות הפתרון ניתן לביצוע ביעילות. במקרה של בעיית החלוקה, כל שיש לעשות הוא לסכום את האיברים בכל אחת משתי הקבוצות ולוודא שהסכום זהה; אם הוא זהה הפתרון נכון, ואחרת הפתרון שגוי. 
כלל זה הוא מאפיין של המחלקה NP, וניתן להגדיר אותה כאוסף הבעיות שלהן קיימת שיטה יעילה לבדוק את נכונותו של פתרון מוצע.
על מנת לתאר בצורה מדויקת את ה"יעילות" של פתרון הבעיות, משתמשים במדד הסיבוכיות הנפוץ ביותר - סיבוכיות זמן ריצה. על מנת למדוד את זמן הריצה של אלגוריתם בלי תלות במימוש האלגוריתם במחשב זה או אחר, נהוג למדוד את זמן הריצה על פי כמות הצעדים הבסיסיים שהאלגוריתם מבצע (זה מצריך הגדרה מדויקת של "צעד בסיסי" - ניתן לצורך כך להשתמש במודל מוסכם של חישוב דוגמת מכונת טיורינג). על פי רוב הגדלת גודל הקלט גורמת להגדלת זמן הריצה של האלגוריתם עליו, ועל כן מתעניינים באופן שבו זמן הריצה גדל ככל שהקלט גדל. במדעי המחשב מקובל כי קצב גידול פולינומי (שניתן לתאר באמצעות פולינום) מייצג סיבוכיות זמן ריצה יעילה (אף כי לא כל אלגוריתם פולינומי הוא אכן מהיר בפועל). הגדרה זו היא הבסיס להגדרת NP, כאוסף הבעיות שקיים אלגוריתם בעל זמן ריצה פולינומי הבודק פתרונות עבורן.
בדיקת פתרונות המתבצעת בזמן יעיל אינה מעידה בהכרח על כך שקל למצוא פתרון בזמן יעיל - למשל, במקרה של בעיית החלוקה, לא מובן מאליו כיצד ניתן למצוא חלוקה מתאימה מבלי לעבור על כל החלוקות האפשריות, שמספרן הוא אקספוננציאלי בגודל הקבוצה, כך שמעבר סדרתי על כולן ידרוש זמן רב מכדי שאלגוריתם זה יוכל להיחשב יעיל. השאלה אם לכל הבעיות שקל לבדוק פתרון עבורן גם קל למצוא פתרון עבורן מכונה שאלת "האם P=NP", ויש לה השלכות תאורטיות ומעשיות רבות.

הגדרת המחלקה NP

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

שקילות ההגדרות לעיל

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

שאלת 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-שלמה ידועה אליה.

בעיות NP-קשות שאינן NP-שלמות

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

המחלקה co-NP

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