21 הבעיות ה-NP שלמות של קארפ
ויקיפדיה האנציקלופדיה encyclopedia
במדעי המחשב, 21 הבעיות ה-NP שלמות של קארפ הן רשימה של 21 בעיות שהציג ריצ'רד קארפ במאמרו משנת 1972, reducibility among combinatorial prolems. המאמר הגיע מעט אחרי פרסום משפט קוק לוין[1], בו הוכח שבעיית הספיקות קשה לפחות כמו כל בעיה אחרת בNP. במאמר הציג קארפ את המושג NP שלמות, והראה על 21 בעיות שהן NP שלמות. מאז הוכחו עוד אלפי בעיות כ-NP שלמות, והשאלה האם P=NP (שהוצגה גם היא במאמר) הפכה לאחת השאלות הפתוחות המרכזיות במדעי המחשב.