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

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

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

בעיות רבות במדעי המחשב ניתנות לניסוח באמצעות שאלות כן/לא - האם אובייקט מסוים מקיים תכונה כלשהי. לדוגמה, בהינתן אוסף של ערים שחלקן מחוברות בכבישים ניתן לשאול אם קיים מסלול המבקר בכל הערים ועובר בכל עיר בדיוק פעם אחת (בניסוח פורמלי זוהי השאלה אם בגרף נתון קיים מסלול המילטוני). דוגמה נוספת היא בעיית החלוקה (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 היא מחלקת השפות הפורמליות^[2] שקיימת עבורן מכונת טיורינג לא דטרמיניסטית, אשר רצה בזמן פולינומי ומכריעה את השפה. ניתן לחשוב על מכונה כנ"ל כעל אלגוריתם שבכל צעד יכול לבחור מבין מספר צעדים אפשריים. האלגוריתם נחשב כ"דוחה" את הקלט אם תמיד יסיים במצב דחייה, בלי תלות בבחירת הצעדים שנעשתה (לעיתים בחירה זו נקראת "מסלול"). מנגד, האלגוריתם נחשב "מקבל" אם קיימת לכל הפחות בחירת צעדים אחת שבסיומה האלגוריתם יסיים במצב "מקבל", כלומר, קיים מסלול מקבל.

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

אם הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle x \in L} אזי קיים מסלול מקבל בריצת הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ M} על הקלט הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ x} .
אם הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle x \not\in L} , כל מסלול ריצה אפשרי של הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ M} על הקלט הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ x} מסתיים במצב דחייה.
מספר הצעדים שעושה המכונה הוא פולינומי ביחס לגודל של x

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

שפה פורמלית הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ L} שייכת למחלקה NP אם קיים אלגוריתם יעיל לבדיקת שייכות מילה ל-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ L} בהינתן "הוכחה" לשייכות זו. דהיינו, בהינתן $\ x\in L$ קיימת "הוכחה" הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ y} "קצרה" כך שאלגוריתם דטרמיניסטי שמקבל כקלט את הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ x,y} ירוץ בזמן פולינומי ולבסוף יפלוט "כן", ואילו אם הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ x\notin L} אז לכל הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ y} אפשרי, אם יוזנו הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ x,y} לאלגוריתם הוא ירוץ בזמן פולינומי ולבסוף יפלוט "לא".

הגדרה זו רחבה יותר מהניסוח הפופולרי של NP בתור מחלקת הבעיות אשר פתרונותיהן ניתנים לאימות באופן יעיל, שכן ה"הוכחה" הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ y} אינה חייבת להיות פתרון של הבעיה, אלא רק מידע שמסייע בהכרעה אם התשובה היא "כן" או "לא". במקרים פשוטים, דוגמת זה של בעיית החלוקה, ההוכחה היא פשוט הצגת הפתרון לבעיה, אך קיימות בעיות שבהן הפתרון אינו כה ברור.

דוגמה לכך היא בדיקת ראשוניות: בהינתן מספר טבעי הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle p} יש להכריע אם הוא ראשוני או לא. כדי להוכיח שמספר נתון אינו ראשוני, די להציג פירוק שלו לשני גורמים לא טריוויאליים, ומכיוון שבדיקה ששניהם גורמים היא במחלקת הסיבוכיות P, הרי שזיהוי מספרים לא ראשוניים הוא בעיה ב-NP. הטענה כי גם בדיקה אם מספר הוא ראשוני שייכת ל-NP היא מעט סבוכה יותר, וניתן להתבסס על משפט מתורת המספרים הקובע כי מספר הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle p} הוא ראשוני אם ורק אם קיים מספר מסדר $p-1$ בחבורת אוילר של p. תנאי זה ניתן לאימות באופן יעיל בהינתן הפירוק של הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle p-1} (הדרוש לבדיקת הסדר). לכן, ההוכחה לראשוניות p תכלול את הפירוק הזה, בצירוף הוכחה (רקורסיבית) כי זהו פירוק מלא (דהיינו כי הגורמים הם ראשוניים) ואת המספר מסדר הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle p-1} .

ניתן להשתמש במושג המתמטי של יחס לצורך תיאור פורמלי של הגדרה זו. את אוסף הקלטים עם ה"הוכחות" שלהם, הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ (x,y)} , מכנים בשם יחס הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ R} . יחס שניתן להכרעה פולינומית הוא יחס שקיימת עבורו מכונת טיורינג דטרמיניסטית הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ M_R} אשר לכל קלט הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ (x,y)} מכריעה בזמן פולינומי אם הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ (x,y)\in R} או לא. לפי טרמינולוגיה זו ניתן להגדיר באופן פורמלי את המחלקה NP:

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle L\in \mbox{NP}} אם קיים יחס

\ R_{L}

, שניתן להכרעה פולינומית, כך שמתקיים

אם הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle x \in L} אזי קיים הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ y} כך ש-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ (x,y)\in R_L} .
אם הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle x \notin L} , אזי לכל הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ y} מתקיים הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ (x,y)\notin R_L} .

היחס נדרש להיות חסום פולינומית כלומר לכל זוג ביחס הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ (x,y)\in R_L} מתקיים הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ |y|\le poly(|x|)} עבור פולינום כלשהו poly (התלוי רק ביחס, לא ב- $\ x$ ).

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

לא קשה להיווכח בשקילות הגדרה זו לקודמותיה: אם נתונה מכונה פולינומית אי דטרמיניסטית הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ M} להכרעת שפה, אז היחס המתאים לשפה זו יכלול זוגות של מילה השייכת לשפה, ו"הוכחה" המורכבת מאוסף הבחירות האי דטרמיניסטיות שמבצעת הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ M} בריצה מקבלת על המילה. בעזרת הוכחה זו (שאורכה פולינומי כי הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ M} פולינומית ולכן מבצעת רק מספר פולינומי של בחירות אי דטרמיניסטיות) יכולה מכונה דטרמיניסטית לבצע סימולציה של הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ M} ולהיווכח בשייכות מילה לשפה.

בכיוון ההפוך, אם קיים יחס הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ R} עבור שפה שהוא חסום פולינומית וניתן לזיהוי פולינומי, אז בהינתן הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ x} , כל שעל מכונה אי דטרמיניסטית לעשות כדי לבדוק את שייכות הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ x} לשפה הוא "לנחש" באופן אי דטרמיניסטי הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ y} ולבדוק בזמן פולינומי אם $\ (x,y)\in R$ . מכיוון ש-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ R} חסום פולינומית, ניחוש הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ y} (אם קיים כזה) אינו מצריך יותר ממספר פולינומי של צעדים.

שאלת P=NP

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

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

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

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

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

הדים לשאלה זו ניתן למצוא כבר במכתב^[3] ששלח קורט גדל לג'ון פון נוימן בשנת 1956, ומאז שנוסחה פורמלית בשנות השבעים היא בעיה פתוחה מרכזית במדעי המחשב, ואחת מ"שבע בעיות המילניום" של מכון קליי למתמטיקה. כל מאמציהם של החוקרים לפתור בעיה זאת עלו בתוהו, והסברה הרווחת בקרב מדעני מחשב העוסקים בבעיה כיום היא כי P≠NP, אך יהיה צורך בגישה חדשה לגמרי כדי לתקוף את הבעיה^[4]. עם זאת, כמה ממדעני המחשב המובילים, כגון דונלד קנות', נוטים להאמין כי P=NP^[5]. בדומה לבעיות פתוחות מפורסמות אחרות, קיימים רבים הטוענים כי הצליחו להוכיח או להפריך את הטענה (או אף הראו שלא ניתן להכריע אותה באמצעות שיטות ההוכחה המקובלות)^[6], אך טענות אלו אינן עומדות בביקורת עמיתים ולא התקבלו על הקהילה המדעית.

בעיות 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 ריצ'רד קארפ שהראה במאמרו^[7] עבור 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 שיש בה לפחות איבר אחד מכל קבוצה?
בעיית תרמיל הגב (KNANPSACK) - בהינתן קבוצת איברים והגדלים שלהם, ותרמיל בגודל נתון, האם ניתן למצוא קבוצת איברים בגודל כולל של לפחות k שניתן להכניס את כולם לתרמיל?
סידור משימות - בהינתן קבוצת משימות, כל אחד ופרק הזמן שלוקח לבצע אותו, האם ניתן לבצע את כולם תוך k זמן על n מחשבים?
בעיית החלוקה (PAR) - בהינתן קבוצת מספרים, האם ניתן לחלק אותם לשתי קבוצות, שסכום כל אחת מהן שווה?
בעיית הפרדה מקסימלית - בהינתן גרף ממושקל, האם ניתן למצוא חלוקה של הגרף לשתי קבוצות, כך שסכום משקלי הקשתות שמחברות ביניהם הוא לפחות k?

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

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

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

בעיה זו ידועה כבעיה שכלל לא ניתנת לחישוב. עם זאת, ניתן לבצע אליה רדוקציה פולינומית מכל בעיה השייכת ל-NP באופן פשוט - בהינתן אלגוריתם הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ A} שפותר (גם אם לא ביעילות) את הבעיה שב-NP, ניתן לשנותו ולקבל אלגוריתם חדש הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ A'} כך שאם אין לבעיה פתרון, הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ A'} ייכנס ללולאה אינסופית (שינוי שכזה קל לבצע בזמן פולינומי, כך שהרדוקציה היא פולינומית). כעת, בהינתן קלט הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ x} לבעיה המקורית, הרדוקציה מחזירה את הצמד הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ (A',x)} .

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

המחלקה co-NP

הגדרתה של NP היא בלתי-סימטרית במהותה: שפה שייכת ל-NP אם לכל מילה השייכת לשפה קיימת "הוכחה" לשייכות זו שניתן לבדוק ביעילות; לעומת זאת, לא נדרש מאום ממילים שאינן שייכות לשפה (פרט לכך שהבודק לא יקבל גם אותן בטעות). ניתן להגדיר מחלקת סיבוכיות מקבילה, בה מתהפכות היוצרות: אם מילה אינה שייכת לשפה קיימת לכך "הוכחה" שמאפשרת לבודק להשתכנע בכך שהמילה אינה בשפה ולדחות אותה (אם כי על "הוכחות" אחרות הוא עשוי לקבל), בעוד שנדרש ממנו לקבל כל מילה שכן שייכת לשפה. דוגמה לשפה שכזו היא שפת הראשוניים שהוזכרה לעיל: בהינתן מספר שאינו ראשוני, "הוכחה" לכך תהיה פשוט מחלק לא טריוויאלי שלו. מחלקת השפות שניתן לבדוק ביעילות "הוכחות" לאי שייכות מילה אליהן מכונה co-NP. פורמלית, ניתן להגדיר אותה כאוסף כל השפות הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ L} כך שמשלימתן הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ \overline{L}} שייכת ל-NP.

לא ידוע אם NP=co-NP. טענה זו חזקה פחות מהטענה כי P=NP; אם P=NP אז נובע מכך מיד כי NP=co-NP=P (שכן P סגורה למשלים) אך ייתכן כי NP=co-NP ועם זאת עדיין הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle P\neq NP} . מצד שני, הוכחה כי הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle NP\neq Co-NP} תגרור מיידית כי גם P שונה מ-NP. ההנחה הרווחת בקרב מדעני המחשב היא כי השוויון אינו מתקיים, והדבר נותן מעמד מיוחד לבעיות השייכות הן ל-NP והן ל-co-NP; אלו בעיות שלא סביר כי הן NP-שלמות שכן הדבר יגרור כי NP=co-NP. הבעיה המפורסמת ביותר השייכת גם ל-NP וגם ל-co-NP היא בעיית הפירוק לגורמים, ותכונה זו שלה הופכת אותה למועמדת הטבעית ביותר לבעיה שמחד אינה שייכת ל-P, (כפי שמקובל להאמין היום) ומאידך אינה NP-שלמה (משפט לדנר^[8] מראה קיום של שפה כזו, בהנחה ש-P שונה מ-NP, אך ההוכחה היא בלכסון ואינה מתארת שפה שצצה באופן "טבעי").

בתרבות

סרט הקולנוע "הסוכן הנוסע" ("Travelling Salesman") (אנ') הוא מותחן שבמרכזו ארבעה מתמטיקאים שנשכרו על ידי ממשלת ארצות הברית כדי לפתור את שאלת P=NP. שם הסרט נלקח מבעיית הסוכן הנוסע, שנכללת במחלקת הסיבוכיות NP.
שאלת P=NP נמצאת במרכז הפרק השני בעונה השנייה של סדרת הטלוויזיה "אלמנטרי", שהיא גרסה מודרנית לעלילות שרלוק הולמס. בפרק זה עוסק הולמס בפענוח רצח של שני מתמטיקאים, שעסקו בחיפוש פתרון לשאלת P=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

הערות שוליים

^ 7 בעיות המילניום, אתר מכון קליי למתמטיקה
^ כל בעיית הכרעה ניתן לתאר כבעיה של זיהוי שייכות של מילה לשפה פורמלית
^ אתר פרס גדל
^ כך למשל קל להראות כי שיטת הלכסון, שבה משתמשים כדי להוכיח כי מחלקות רבות שונות זו מזו (למשל בבעיית העצירה ובמשפטי ההיררכיה), ככל הנראה אינה מסוגלת להתמודד עם בעיה זו (Sipser, עמוד 349)
^ ריאיון עם דונלד קנות' - informit.com, שאלה 17
^ The P-versus-NP page - שלל מאמרים הטוענים לפתרון בעיית P=NP
^ Richard Karp,"Reducibility Among Combinatorial Problems", Complexity of computer computations, 1972
^ Ladner, Richard (1975). "On the Structure of Polynomial Time Reducibility". Journal of the ACM (JACM). 22 (1): 155–171. doi:10.1145/321864.321877.

הערך באדיבות ויקיפדיה העברית, קרדיט,
רשימת התורמים
רישיון cc-by-sa 3.0

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

[1] 7 בעיות המילניום, אתר מכון קליי למתמטיקה

[2] כל בעיית הכרעה ניתן לתאר כבעיה של זיהוי שייכות של מילה לשפה פורמלית

[3] אתר פרס גדל

[4] כך למשל קל להראות כי שיטת הלכסון, שבה משתמשים כדי להוכיח כי מחלקות רבות שונות זו מזו (למשל בבעיית העצירה ובמשפטי ההיררכיה), ככל הנראה אינה מסוגלת להתמודד עם בעיה זו (Sipser, עמוד 349)

[5] ריאיון עם דונלד קנות' - informit.com, שאלה 17

[6] The P-versus-NP page - שלל מאמרים הטוענים לפתרון בעיית P=NP

[7] Richard Karp,"Reducibility Among Combinatorial Problems", Complexity of computer computations, 1972

[8] Ladner, Richard (1975). "On the Structure of Polynomial Time Reducibility". Journal of the ACM (JACM). 22 (1): 155–171. doi:10.1145/321864.321877.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

מחלקות סיבוכיות חשובות (נוספות)
נחשב מעשי	NL • P • ZPP • RP • BPP • BQP • PTAS • APX
ככל הנראה בלתי מעשי	NP‏ • NP-קשיות • co-NP ‏ • PP ‏ • #P ‏ • PSPACE
נחשב כבלתי מעשי	EXPTIME • NEXPTIME • ‏EXPSPACE • ‏ELEMENTARY • ‏PR • ‏R • ‏RE • ‏ALL
היררכית מחלקות	ההיררכיה הפולינומית • ההיררכיה האקספוננציאלית • ההיררכיה הבוליאנית • ההיררכיה האריתמטית • היררכית גרזגרצ'יק
משפחות של מחלקות	מערכת הוכחה אינטראקטיבית • ‏DTIME • NTIME • ‏DSPACE • ‏NSPACE

בעיות המילניום של מכון קליי
הבעיות	השערת בירץ' וסווינרטון-דייר • השערת רימן • השערת פואנקרה (נפתרה) • השערת הודג' • משוואות נאוויה-סטוקס • P=NP • תורות יאנג-מילס
פותרים	גריגורי פרלמן (השערת פואנקרה)
23 הבעיות של הילברט • בעיות לנדאו