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

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

מחלקת NP בהנחה ש-P = 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)"‏.

הגדרה באמצעות מכונות אי דטרמיניסטיות

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

פורמלית, $\ L\in {\mbox{NP}}$ אם קיימת מכונת טיורינג אי דטרמיניסטית, פולינומית, $\ M$ כך שמתקיים:

• אם $x\in L$ אזי קיים מסלול מקבל בריצת $\ M$ על הקלט $\ x$.
• אם $x\not \in L$, כל מסלול ריצה אפשרי של $\ M$ על הקלט $\ x$ מסתיים במצב דחייה.
• מספר הצעדים שעושה המכונה הוא פולינומי ביחס לגודל של x

הגדרה באמצעות יחסים

שפה פורמלית $\ L$ שייכת למחלקה NP אם קיים אלגוריתם יעיל לבדיקת שייכות מילה ל-$\ L$ בהינתן "הוכחה" לשייכות זו. דהיינו, בהינתן $\ x\in L$ קיימת "הוכחה" $\ y$ "קצרה" כך שאלגוריתם דטרמיניסטי שמקבל כקלט את $\ x,y$ ירוץ בזמן פולינומי ולבסוף יפלוט "כן", ואילו אם $\ x\notin L$ אז לכל $\ y$ אפשרי, אם יוזנו $\ x,y$ לאלגוריתם הוא ירוץ בזמן פולינומי ולבסוף יפלוט "לא".

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

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

ניתן להשתמש במושג המתמטי של יחס לצורך תיאור פורמלי של הגדרה זו. את אוסף הקלטים עם ה"הוכחות" שלהם, $\ (x,y)$, מכנים בשם יחס $\ R$. יחס שניתן להכרעה פולינומית הוא יחס שקיימת עבורו מכונת טיורינג דטרמיניסטית $\ M_{R}$ אשר לכל קלט $\ (x,y)$ מכריעה בזמן פולינומי אם $\ (x,y)\in R$ או לא. לפי טרמינולוגיה זו ניתן להגדיר באופן פורמלי את המחלקה NP:

$L\in {\mbox{NP}}$ אם קיים יחס $\ R_{L}$, שניתן להכרעה פולינומית, כך שמתקיים

• אם $x\in L$ אזי קיים $\ y$ כך ש-$\ (x,y)\in R_{L}$.
• אם $x\notin L$, אזי לכל $\ y$ מתקיים $\ (x,y)\notin R_{L}$.

היחס נדרש להיות חסום פולינומית כלומר לכל זוג ביחס $\ (x,y)\in R_{L}$ מתקיים $\ |y|\leq poly(|x|)$ עבור פולינום כלשהו poly (התלוי רק ביחס, לא ב-$\ x$).

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

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

בכיוון ההפוך, אם קיים יחס $\ R$ עבור שפה שהוא חסום פולינומית וניתן לזיהוי פולינומי, אז בהינתן $\ x$, כל שעל מכונה אי דטרמיניסטית לעשות כדי לבדוק את שייכות $\ x$ לשפה הוא "לנחש" באופן אי דטרמיניסטי $\ y$ ולבדוק בזמן פולינומי אם $\ (x,y)\in R$. מכיוון ש-$\ R$ חסום פולינומית, ניחוש $\ y$ (אם קיים כזה) אינו מצריך יותר ממספר פולינומי של צעדים.

שאלת 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-שלמות של קארפ

ערך מורחב – 21 הבעיות ה-NP שלמות של קארפ

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

להלן הבעיות שתיאר קארפ במאמרו, ומהוות דוגמאות "קלאסיות" לבעיות NP-שלמות:

• בעיית SAT בהינתן נוסחה בתחשיב הפסוקים שמכילה רק קשרים מסוג "גם", "או" ו-"לא", האם קיימת השמה של ערכי אמת למשתנים כך שהנוסחה תקבל ערך אמת?
• בעיית תת-גרף מלא (גרף מלא הוא גרף אשר כל שני צמתים בו מחוברים על ידי קשת, ראו גם קבוצת קודקודים בלתי תלויה)
• בעיית תת-קבוצות זרות – בהינתן תת-קבוצות של קבוצה מסוימת, האם יש k קבוצות זרות?
• בעיית כיסוי קודקודים (VC) – בהינתן גרף, האם יש k קודקודים שמכסים את כל הקשתות?
• בעיית כיסוי קבוצות – בהינתן תתי קבוצות של קבוצה נתונה, האם יש k קבוצות שאיחודן הוא כל הקבוצה?
• בעיית FAS – בהינתן גרף מכוון, האם ניתן לקבל גרף ללא מעגלים על ידי הוצאת k קשתות לכל היותר?
• בעיית FVS – בהינתן גרף לא מכוון, האם ניתן לקבל גרף ללא מעגלים על ידי הוצאת k קודקודים לכל היותר?
• מסלול המילטוני מכוון – בהינתן גרף מכוון, האם יש בו מסלול המילטוני? (מסלול המילטוני הוא מסלול בגרף העובר בכל צומת בדיוק פעם אחת)
• מסלול המילטוני לא מכוון – בהינתן גרף לא מכוון, האם יש בו מסלול המילטוני?
• תכנון ליניארי בשלמים – בהינתן מערכת אי שוויונות, האם יש פתרון שבו כל המשתנים מקבלים ערכים שלמים?
• בעיית 3-SAT – בהינתן נוסחת CNF בה בכל פסוקית יש 3 משתנים, האם היא ניתנת לסיפוק?
• צביעת גרף – בהינתן גרף, האם ניתן לצבוע אותו ב-k צבעים (כאשר k הוא לפחות 3), כאשר כל קשת מחברת בין קודקודים שאינם מאותו צבע?
• כיסוי קליקות – בהינתן גרף, האם ניתן לכסות את כל הקשתות שלו בעזרת k קליקים?
• כיסוי מדויק – בהינתן תתי-קבוצות של קבוצה, האם ניתן למצוא קבוצות זרות שאיחודן הוא כל הקבוצה?
• התאמה 3-ממדים (3DM) – בהינתן 3 קבוצות בגודל n, וקבוצות שלשות כך שהאיבר הראשון נמצא בקבוצה הראשונה וכו', האם קיימת קבוצה של n שלשות שמכסות את כל הקבוצות?
• עץ סטיינר – בהינתן n נקודות במישור, האם ניתן לחבר אותם בעזרת קטעים שסכום האורכים קטן מ-k?
• בעיית Hitting Set (HS) – בהינתן קבוצה של קבוצות, האם קיימת קבוצה שאיננה גדולה מ-k שיש בה לפחות איבר אחד מכל קבוצה?
• בעיית תרמיל הגב (Knapsack) – בהינתן קבוצת איברים והגדלים שלהם, ותרמיל בגודל נתון, האם ניתן למצוא קבוצת איברים בגודל כולל של לפחות k שניתן להכניס את כולם לתרמיל?
• סידור משימות – בהינתן קבוצת משימות, כל אחד ופרק הזמן שלוקח לבצע אותו, האם ניתן לבצע את כולם תוך k זמן על n מחשבים?
• בעיית החלוקה (PAR) – בהינתן קבוצת מספרים, האם ניתן לחלקה לשתי קבוצות שלגביהן, סכום איברי אחת מהן שווה לזה של איברי השנייה?
• בעיית הפרדה מקסימלית – בהינתן גרף ממושקל, האם ניתן למצוא חלוקה של הגרף לשתי קבוצות, כך שסכום משקלי הקשתות שמחברות ביניהם הוא לפחות k?

כפי שצוין, ניתן להוכיח שעוד אלפי בעיות אחרות הן NP-שלמות, על ידי רדוקציה פולינומית מבעיה אחרת שהוכחה כ־NP-שלמה.

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

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

בעיה זו ידועה כבעיה שכלל לא ניתנת לחישוב. עם זאת, ניתן לבצע אליה רדוקציה פולינומית מכל בעיה השייכת ל-NP באופן פשוט – בהינתן אלגוריתם $\ A$ שפותר (גם אם לא ביעילות) את הבעיה שב-NP, ניתן לשנותו ולקבל אלגוריתם חדש $\ A'$ כך שאם אין לבעיה פתרון, $\ A'$ ייכנס ללולאה אינסופית (שינוי שכזה קל לבצע בזמן פולינומי, כך שהרדוקציה היא פולינומית). כעת, בהינתן קלט $\ x$ לבעיה המקורית, הרדוקציה מחזירה את הצמד $\ (A',x)$.

קשרים עם מחלקות סיבוכיות דומות

המחלקה co-NP

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

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

בתרבות

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

ראו גם

• מחלקת סיבוכיות
• co-NP
• מערכת הוכחה אינטראקטיבית
• מחשב קוונטי
• NP ביניים

לקריאה נוספת

• סיימון סינג, סודות ההצפנה (מאנגלית: The Code Book), הוצאת משכל (ספרי חמד וידיעות אחרונות), 2003
• דוד הראל, המחשב אינו כל-יכול, הוצאת ידיעות אחרונות, 2004

• Michael Sipser, Introduction to the Theory of Computation, PWS Publishing Company, 1997.
• Oded Goldreich, P, NP, and NP-Completeness: The Basics of Computational Complexity, Cambridge University Press, 2010

קישורים חיצוניים

• גדי אלכסנדרוביץ', אז מה זה עניין P=NP, בעצם?, באתר "לא מדויק", 15 באוגוסט 2010
• גדי אלכסנדרוביץ', משפט לדנר, באתר "לא מדויק", 10 בנובמבר 2010
• NP, באתר MathWorld (באנגלית)