8. Сводимости используемые при доказательстве np-полноты

SAT – задача о выполнимости логической функции;

3CNF – трёх конъюнктивно нормальная форма;

CLIQUE – задача о нахождении максимальной клики на графе;

VERTEX-COVER – задача о минимально возможном вершинном покрытии;

SUBSET-SUM – известная нам уже задача о монетах;

HAM-CYCLE – гамильтонов цикл;

TSP – travel sensement problem – задача коммивояжёра.