Изменения

Перейти к: навигация, поиск

NP-полнота задачи о независимом множестве

73 байта убрано, 20:08, 15 марта 2010
м
Задача о независимом множестве является NP-трудной
<math>(\overline{x}\lor y\lor z)\land (x \lor y \lor \overline{z}) \to</math>[[Файл:IND_GRAPH.png]]
Докажем, что формула выполнима тогда и только тогда, когда в соответствующем графе есть независимое множество из <math>k</math> вершин. Пусть формула выполнима, тогда в каждой скобке есть хотя бы одна переменная, принимающая значение “правда” (учитываем отрицание, если оно есть). Выберем соответствующую переменную в качестве вершины в графе. Выбранное множество вершин является независимым, так как ребрами соединены только те вершины, которые соответствуют переменным из одной скобки(а мы выбирали только одну переменную из каждой скобки) и пары вершин, которым соответствуют пары переменных вида <math>x,\overline{x}</math>, которые не могут одновременно принимать значение “правда”. Пусть в графе есть независимое множество, размера <math>k</math>. Тогда в каждой тройке вершин, соответствующих некоторой скобке, выбрана ровно одна вершина. Установим значение соответствующей переменной “правда”. Тогда в каждой скобке, будет хотя бы одна переменная, имеющая значение “правда”, значит вся формула будет принимать значение “правда”. Построение по формуле соответствующего графа можно сделать за полиномиальное время.
===Задача о независимом множестве принадлежит классу NP===
В качестве сертификата возьмем набор из <math>k</math> вершин. За время <math>O(k^2)</math> можно проверить, является ли данное множество вершин независимым.
43
правки

Навигация