NP היא מחלקה של שפות שיש להן מאמת זמן פולינומי
המחלקה NP, המייצגת "זמן פולינומי לא דטרמיניסטי", היא מושג בסיסי בתורת המורכבות החישובית, תת-תחום של מדעי המחשב התיאורטיים. כדי להבין NP, צריך קודם כל להבין את הרעיון של בעיות החלטה, שהן שאלות עם תשובה של כן או לא. שפה בהקשר זה מתייחסת לקבוצת מחרוזות מעל אלפבית כלשהו, כאשר כל מחרוזת מקודדת מופע של בעיית החלטה.
אומרים ששפה (L) נמצאת ב-NP אם קיים מאמת זמן פולינומי עבור (L). מאמת הוא אלגוריתם דטרמיניסטי (V) שלוקח שתי כניסות: מופע (x) ותעודה (y). התעודה (y) ידועה גם כ"עד" או "הוכחה". המאמת (V) בודק אם האישור (y) מאשר ש-(x) שייך לשפה (L). באופן פורמלי, שפה (L) נמצאת ב-NP אם קיים אלגוריתם פולינום-זמן (V) ופולינום (p(n)) כך שלכל מחרוזת (x ב-L), קיימת מחרוזת (y) עם ( |y|. leq p(|x|)) ו-(V(x, y) = 1). לעומת זאת, עבור כל מחרוזת (x notin L), אין מחרוזת (y) כזו ש(V(x,y) = 1).
כדי להבהיר מושג זה, שקול את הבעיה הידועה של "סיפוק בוליאני" (SAT). בעיית SAT שואלת האם קיימת הקצאה של ערכי אמת למשתנים בנוסחה בוליאנית נתונה כך שהנוסחה מוערכת כאמת. בעיית ה-SAT היא ב-NP מכיוון שבהינתן נוסחה בוליאנית (phi) והקצאה (אלפא) של ערכי אמת למשתנים שלה, אפשר לאמת בזמן פולינומי אם (אלפא) מספק (phi). כאן, המופע ( x ) הוא הנוסחה הבוליאנית ( phi ), והתעודה ( y ) היא המשימה ( אלפא ). המאמת ( V ) בודק אם ( אלפא ) הופך את ( phi ) לנכון, דבר שניתן לעשות בזמן פולינום ביחס לגודל של ( phi ).
דוגמה נוספת להמחשה היא בעיית "הנתיב ההמילטוני". בעיה זו שואלת האם קיים נתיב בגרף נתון שמבקר בכל קודקוד בדיוק פעם אחת. בעיית הנתיב המילטון היא גם ב-NP כי בהינתן גרף (G) ורצף של קודקודים (P), אפשר לאמת בזמן פולינומי אם (P) הוא נתיב המילטון ב-(G). במקרה זה, המופע ( x ) הוא הגרף ( G ), והתעודה ( y ) היא רצף הקודקודים ( P ). המאמת ( V ) בודק האם ( P ) יוצר נתיב המילטון, מה שניתן לעשות בזמן פולינום ביחס לגודל של ( G ).
הרעיון של אימות בזמן פולינום חשוב מכיוון שהוא מספק דרך לאפיין בעיות שניתן לבדוק ביעילות, גם אם מציאת הפתרון עשויה להיות בלתי ניתנת לביצוע מבחינה חישובית. זה מוביל לשאלה המפורסמת האם ( P = NP ), ששואלת האם כל בעיה שניתן לאמת את פתרונה בזמן פולינום ניתנת לפתרון גם בזמן פולינומי. המחלקה (P) מורכבת מבעיות החלטה שניתן לפתור בזמן פולינום על ידי מכונת טיורינג דטרמיניסטית. אם ( P = NP ), זה אומר שלכל בעיה עם מאמת זמן פולינומי יש גם פותר זמן פולינומי. שאלה זו נותרה אחת הבעיות הפתוחות החשובות ביותר במדעי המחשב.
אחת מתכונות המפתח של NP היא שהוא סגור תחת הפחתות זמן פולינומיות. הפחתת זמן פולינום משפה ( L_1 ) לשפה ( L_2 ) היא פונקציה ניתנת לחישוב בזמן פולינום ( f ) כך ש- ( x ב L_1 ) אם ורק אם ( f(x) ב L_2 ). אם קיימת הפחתת זמן פולינומית מ- ( L_1 ) ל- ( L_2 ) ו- ( L_2 ) היא ב-NP, אז ( L_1 ) היא גם ב-NP. תכונה זו מסייעת בחקר שלמות ה-NP, המזהה את הבעיות ה"קשות" ביותר ב-NP. בעיה היא NP-שלמה אם היא ב-NP וכל בעיה ב-NP יכולה להיות מופחתת אליה בזמן פולינומי. בעיית ה-SAT הייתה הבעיה הראשונה שהוכחה כ-NP-שלמה, והיא משמשת בסיס להוכחת ה-NP-שלמותן של בעיות אחרות.
כדי להמחיש עוד יותר את הרעיון של אימות בזמן פולינומי, שקול את בעיית "סכום המשנה". בעיה זו שואלת האם קיימת תת-קבוצה של קבוצה נתונה של מספרים שלמים המסכמת לערך יעד מוגדר. בעיית סכום המשנה היא ב-NP מכיוון שבהינתן קבוצה של מספרים שלמים ( S ), ערך יעד ( t ) ותת קבוצה ( S' ) של ( S ), ניתן לאמת בזמן פולינום אם סכום האלמנטים ב (S') שווה (t). כאן, המופע ( x ) הוא הזוג ( (S, t) ), והתעודה ( y ) היא קבוצת המשנה ( S' ). המאמת ( V ) בודק האם סכום האלמנטים ב- ( S' ) שווה ל- ( t ), מה שניתן לעשות בזמן פולינום ביחס לגודל של ( S ).
החשיבות של אימות זמן פולינום חורגת מעבר לשיקולים תיאורטיים. מבחינה מעשית, זה אומר שלבעיות ב-NP, אם ניתנת פתרון מוצע (תעודה), ניתן לבדוק זאת ביעילות. יש לכך השלכות משמעותיות על פרוטוקולים קריפטוגרפיים, בעיות אופטימיזציה ותחומים שונים בהם אימות נכונות הפתרון חשוב.
לסיכום, המחלקה NP מקיפה בעיות החלטה שעבורן ניתן לאמת פתרון מוצע בזמן פולינומי על ידי אלגוריתם דטרמיניסטי. מושג זה הוא יסוד בתיאוריית המורכבות החישובית ויש לו השלכות עמוקות הן על היבטים תיאורטיים והן על היבטים מעשיים של מדעי המחשב. חקר NP, אימות בזמן פולינומי ומושגים קשורים כמו NP-שלמות ממשיך להיות תחום מחקר תוסס וקריטי.
שאלות ותשובות אחרונות אחרות בנושא מוּרכָּבוּת:
- האם מחלקה PSPACE לא שווה למחלקה EXPSPACE?
- האם מחלקת המורכבות P היא תת-קבוצה של מחלקת PSPACE?
- האם נוכל להוכיח שמחלקות Np ו-P זהות על ידי מציאת פתרון פולינום יעיל לכל בעיה שלמה של NP ב-TM דטרמיניסטי?
- האם מחלקת NP יכולה להיות שווה למחלקה EXPTIME?
- האם יש בעיות ב-PSPACE שעבורן אין אלגוריתם NP ידוע?
- האם בעיית SAT יכולה להיות בעיה שלמה של NP?
- האם בעיה יכולה להיות במחלקת מורכבות NP אם יש מכונת טיורינג לא דטרמיניסטית שתפתור אותה בזמן פולינומי
- האם P ו-NP הם בעצם אותה דרגת מורכבות?
- האם כל הקשר הוא שפה חופשית בשיעור המורכבות P?
- האם יש סתירה בין ההגדרה של NP כמחלקה של בעיות החלטה עם מאמת זמן פולינום לבין העובדה שלבעיות במחלקה P יש גם מאמת זמן פולינומי?
צפו בשאלות ותשובות נוספות ב-Complexity