21 NP-повна задача Карпа

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

Список Карпа — список, що складається з формулювання та доведення NP-повноти 21 задачі, опублікований Річардом Карпом у 1972 році у своїй праці «Зводимість між комбінаторними задачами» (англ. «Reducibility Among Combinatorial Problems»)[1].

Список задач[ред.ред. код]

Див. також[ред.ред. код]

Посилання[ред.ред. код]

  1. «Reducibility Among Combinatorial Problems», Р. Карп, 1972 рік (англ.)