NP (מחלקת סיבוכיות) – הבדלי גרסאות
תוכן שנמחק תוכן שנוסף
←שאלת P=NP: ניסוחים |
|||
שורה 50:
שאלה זו אינה בעלת ערך [[אקדמיה|אקדמי]] בלבד. עם התפתחות השימושים המסחריים של ה[[קריפטוגרפיה]] בעידן ה[[מחשב]], ובמיוחד ב[[מסחר אלקטרוני]], הפכה התשובה לשאלה לבעלת חשיבות [[כלכלה|כלכלית]] לא מבוטלת. הסיבה לכך היא שרוב המסחר האלקטרוני ותעשיית האבטחה הדיגיטלית מסתמכים על [[אלגוריתם|אלגוריתמים]] שיכולת ההצפנה שלהם נובעת מחוסר היכולת הנוכחי לפתור בעיות NP בזמן סביר. דוגמה נפוצה היא אלגוריתם ה[[הצפנה]] [[RSA]], שמבוסס על כך שלא ידוע פתרון פולינומי ל[[פירוק מספר שלם לגורמים|פירוק לגורמים]] של מכפלת שני מספרים ראשוניים, ולכן פירוק שכזה דורש זמן רב מאוד כאשר המספרים הראשוניים שנבחרו הם גדולים מספיק. עם זאת, אף אם P אינו שווה ל-NP, עדיין ייתכן פירוק מהיר לגורמים.
למעשה, אם יוכח ש-P=NP הדבר ינחית מכה קשה מאוד על הקריפטוגרפיה כולה. למשל, הדבר יראה כי לא קיימות [[פונקציה חד-כיוונית|פונקציות חד-כיווניות]], כלומר הצפנת [[מפתח ציבורי]] אינה אפשרית שכן קל לזהות שכתב גלוי הוצפן לכתב סתר נתון באמצעות מפתח ציבורי (פשוט מצפינים את הכתב הגלוי בעזרת המפתח ומשווים לכתב הסתר), ומכאן שאם זיהוי יעיל גורר חיפוש יעיל, הרי שבהינתן הודעה מוצפנת והמפתח הציבורי שהצפין אותה, ניתן יהיה למצוא ביעילות את הכתב הגלוי המקורי. השלכה נוספת של הוכחת השוויון P=NP תהיה הוכחת אי קיומם של [[מחולל מספרים פסאודו-אקראיים|מחוללים פסאודו-אקראיים]] אמיתיים (דהיינו, הדבר יראה שהמחוללים שנמצאים כיום בשימוש אינם מקיימים את מלוא התכונות הנדרשות מהם, ושלא יכולים להתקיים מחוללים שכן מקיימים תכונות אלו).
תחום נוסף
הדים לשאלה זו ניתן למצוא כבר במכתב{{הערה|[http://sigact.acm.org/prizes/godel/ אתר פרס גדל]}} ששלח [[קורט גדל]] ל[[ג'ון פון נוימן]] בשנת [[1956]], ומאז שנוסחה פורמלית בשנות השבעים היא [[בעיה פתוחה]] מרכזית במדעי המחשב, ואחת מ"[[שבע בעיות המילניום]]" של [[מכון קליי למתמטיקה]]. כל מאמציהם של החוקרים לפתור בעיה זאת עלו בתוהו, והסברה הרווחת בקרב מדעני מחשב העוסקים בבעיה כיום היא כי P≠NP, אך יהיה צורך בגישה חדשה לגמרי כדי לתקוף את הבעיה{{הערה|כך למשל קל להראות כי שיטת הלכסון, שבה משתמשים כדי להוכיח כי מחלקות רבות שונות זו מזו (למשל ב[[בעיית העצירה]] וב[[סיבוכיות מקום#משפטי היררכיה|משפטי ההיררכיה]]), ככל הנראה אינה מסוגלת להתמודד עם בעיה זו (Sipser, עמוד 349)}}. עם זאת, כמה ממדעני המחשב המובילים, כגון [[דונלד קנות']], נוטים להאמין כי P=NP{{הערה|[http://www.informit.com/articles/article.aspx?p=2213858 ריאיון עם דונלד קנות'] - informit.com, שאלה 17}}. בדומה לבעיות פתוחות מפורסמות אחרות, קיימים רבים הטוענים כי הצליחו להוכיח או להפריך את הטענה (או אף הראו שלא ניתן להכריע אותה באמצעות שיטות ההוכחה המקובלות){{הערה|[http://www.win.tue.nl/~gwoegi/P-versus-NP.htm The P-versus-NP page] - שלל מאמרים הטוענים לפתרון בעיית P=NP}}, אך טענות אלו אינן עומדות בביקורת עמיתים ולא התקבלו על הקהילה המדעית.
| |||