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