P=NP

מתוך ויקיפדיה, האנציקלופדיה החופשית

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

תוכן עניינים 1 המחלקות P ו-NP 2 דוגמה 3 ההשלכות המעשיות של הבעיה 4 ראו גם 5 לקריאה נוספת

[עריכה] המחלקות P ו-NP

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

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

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

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

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

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

[עריכה] דוגמה

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

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

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

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

[עריכה] ההשלכות המעשיות של הבעיה

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

[עריכה] ראו גם

• co-NP

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

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