בעיית P=NP

מתוך ויקיפדיה, האנציקלופדיה החופשית
(הופנה מהדף 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[עריכת קוד מקור | עריכה]

Postscript-viewer-shaded.png ערך מורחב – 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. בהינתן פתרון מוצע - חלוקה של שתי קבוצות - כל שנדרש הוא לחבר את המספרים בכל אחת משתי הקבוצות, ולבדוק האם סכומן זהה.

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

ראו גם[עריכת קוד מקור | עריכה]

קישורים חיצוניים[עריכת קוד מקור | עריכה]

לקריאה נוספת[עריכת קוד מקור | עריכה]

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