Версия от 14:15, 14 сентября 2016

NP-полные задачи

На лекциях и семинарах обсуждалась NP-полнота следующих задач:

выполнимость булевой формулы (SAT);
выполнимость 3-КНФ (3SAT);
существование означивания для 3-КНФ, дающего не менее одной истинной и не менее одной ложной литеры в каждой скобке (Not-All-Equal-3SAT);
существование клики заданного размера в графе;
существование вершинного покрытия заданного размера в графе;
существование независимого множества заданного размера в графе;
наличие гамильтонова пути в ориентированном графе;
наличие гамильтонова цикла в ориентированном графе;
существование раскраски графа в три цвета, такой что никакие две смежные вершины не окрашены в один цвет;
наличие разреза размера не менее заданного в неориентированном графе;
возможность корректной расстановки мин в игре "Сапер" на произвольном неориентированном графе;
задача о сумме подмножества;
задача о рюкзаке.

Всеми этим задачами можно пользоваться для доказательства NP-полноты других задач (если явно не указано иное).

@@ Строка 8: / Строка 8: @@
 * существование клики заданного размера в графе;
 * существование вершинного покрытия заданного размера в графе;
+* существование независимого множества заданного размера в графе;
 * наличие гамильтонова пути в ориентированном графе;
 * наличие гамильтонова цикла в ориентированном графе;