משתמש:דניאל ב./P=NP

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

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