בעיית P=NP

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

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

היסטוריה

בשנת 1955, ג'ון נאש שלח מכתב ל-NSA בו הוא ציין כי הוא חושד שלפרוץ קוד מסובך מספיק זמן ריצה אקספוננציאלי ביחס לאורך המפתח (דבר זה שקול לכך ש-P ≠ NP). בשנת 1956, במכתב בינו ובין ג'ון פון נוימן, קורט גדל שאל האם ניתן להוכיח הוכחות מתמטיות בזמן ליניארי או ריבועי וכתוצאה מכך יהיה אפשר להפוך הוכחות לדבר אוטומטי. התכתבויות אלו הופיעו לפני 1971 בו הביאו ההגדרות הפורמליות למושגי P ו-NP ולבעיית P=NP על ידי סטיבן קוק במאמרו "The complexity of theorem proving procedures". בשנת 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? (בעיות פתוחות נוספות במדעי המחשב)

• מחלקת סיבוכיות
• co-NP

לקריאה נוספת

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

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

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