Алгоритмы и структуры данных 2 2016/2017/152-2

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

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

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

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