פורטל:תוכנה/הידעת?/12

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

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