NP (מחלקת סיבוכיות)

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

מחלקת NP בהנחה ש-P = NP (מימין) ובהנחה ש-P ≠ NP (משמאל)
Other Languages