בעיית P=NP

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

דיאגרמת אוילר המציגה את 2 האופציות עבור P=NP או NP≠P

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

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

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

לפתרון הבעיה ישנן השלכות תאורטיות ומעשיות רבות, והיא זכתה להכרה כאחת מ"שבע בעיות המילניום" של מכון קליי למתמטיקה.

היסטוריה

בשנת 1955 שלח ג'ון נאש מכתב ל-NSA בו הוא ציין כי הוא חושד שכדי לפרוץ קוד מסובך מספיק זמן ריצה אקספוננציאלי ביחס לאורך המפתח.^[2] בשנת 1956, שאל קורט גדל במכתב בינו ובין ג'ון פון נוימן, האם ניתן להוכיח הוכחות מתמטיות בזמן ליניארי או ריבועי וכתוצאה מכך יהיה אפשר להפוך הוכחות לדבר אוטומטי.^[3] התכתבויות אלו הופיעו לפני 1971, השנה שבה נכתבו ההגדרות הפורמליות למושגי P ו-NP ולבעיית P=NP על ידי סטיבן קוק במאמרו "The complexity of theorem proving procedures".^[4] בשנת 2000 נבחרה הבעיה להיות אחת מתוך 7 בעיות המילניום של מכון קליי, ואדם אשר פותר אותה יקבל פרס של מיליון דולרים אמריקאים ממכון זה.

המחלקות P ו-NP

ערכים מורחבים – P (מחלקת סיבוכיות), NP (מחלקת סיבוכיות)

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

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

לקבוצה P (מלשון Polynomial) שייכת כל בעיית הכרעה שעבורה קיים אלגוריתם המוצא פתרון בזמן ריצה פולינומי.

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

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

אם כן, בעיית P=NP שואלת האם קל למצוא את הפתרונות של בעיה חישובית שקל לבדוק את הפתרונות שלה. התשובה לכך אינה ידועה, אך ההשערה הרווחת היא ש- P ≠ NP, כלומר, קיימות בעיות שקל לבדוק וקשה לפתור.

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

דוגמה

בהינתן קבוצה של מספרים שלמים, נדרש לקבוע האם ניתן לחלקה לשתי קבוצות של מספרים כך שסכומן זהה (בעיה זו נקראת בעיית החלוקה, Partition Problem). לדוגמה, הקבוצה {1, 3, 4, 5, 8, 11} ניתנת לחלוקה לשתי קבוצות: הקבוצה {11, 5} והקבוצה {1, 3, 4, 8}, שסכום כל אחת מהן הוא 16. מאידך, הקבוצה {1, 3, 5, 6} לא ניתנת לחלוקה כזו.

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

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

ההיררכיה הפולינומית

ערכים מורחבים – ההיררכיה הפולינומית

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

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

הגדרת ההיררכיה מתקבלת ישירות מההגדרה על פי כמתים - בדרגה ה-i בהיררכיה, תופענה מחלקות הסיבוכיות עם i כמתים. נשים לב שיש בדיוק 2 מחלקות בכל דרגה, המסומנות $\Sigma _{i},\Pi _{i}$ . ההיררכיה נקראת פולינומית מכיוון שכל אחד מהערכים הקשורים (כלומר, הערכים הנמצאים בצמידות לכמת) מוגבלים להיות באורך פולינומי באורך הקלט. ההיררכיה נקראת היררכיה מכיוון שכל המחלקות בדרגה ה- $i-1$ מוכלות במחלקה שבדרגה ה-i. נשים לב, שבהצגה זו SAT היא באופן טריוויאלי שפה NP-שלמה.

הקרסת ההיררכיה היא הוכחה שעבור דרגה מסוימת בהיררכיה, מתקיים $\Sigma _{i}=\Pi _{i}$ , אזי $PH=\Sigma _{i}=\Pi _{i}$ . משפט זה שימושי מסיבות רבות. באופן מופשט - אם נוכיח שההיררכיה אינה קורסת תחת דרגה מסוימת, אזי $P\neq NP$ .

משפט הקרסת ההיררכיה שימושי באופן נוסף - מספיק להוכיח ש- $P\neq \Sigma _{i}$ , והתוצאה המיידית היא ש-P שונה מ-NP.

ראו גם

בעיות פתוחות במדעי המחשב:

האם NP = P?
(בעיות פתוחות נוספות במדעי המחשב)

לקריאה נוספת

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

Oded Goldreich, P, NP, and NP-Completeness: The Basics of Computational Complexity, Cambridge University Press, 2010

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

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

הערות שוליים

^ Lance Fortnow, The status of the P versus NP problem, Communications of the ACM 52, 2009-09, עמ' 78–86 doi: 10.1145/1562164.1562186
^ John Nash, "Letters from John Nash", NSA, ‏2012
^ Juris Hartmanis, "Gödel, von Neumann, and the P = NP problem", Bulletin of the European Association for Theoretical Computer Science, ‏101-107
^ Stephen A. Cook, The complexity of theorem-proving procedures, ACM Press, 1971, עמ' 151–158 doi: 10.1145/800157.805047

[1] Lance Fortnow, The status of the P versus NP problem, Communications of the ACM 52, 2009-09, עמ' 78–86 doi: 10.1145/1562164.1562186

[2] John Nash, "Letters from John Nash", NSA, ‏2012

[3] Juris Hartmanis, "Gödel, von Neumann, and the P = NP problem", Bulletin of the European Association for Theoretical Computer Science, ‏101-107

[4] Stephen A. Cook, The complexity of theorem-proving procedures, ACM Press, 1971, עמ' 151–158 doi: 10.1145/800157.805047

[1]

[2]

[3]

[4]