Список Карпа — список из 21 NP-полных задач, опубликованный Ричардом Карпом в 1972 году в работе «Сводимость комбинаторных задач»[1], в которой приведены как формулировки, так и доказательства NP-полноты для каждой: