Изменения

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

NP-полнота задачи о выполнимости булевой формулы в форме 3-КНФ

143 байта убрано, 17:56, 17 марта 2010

Нет описания правки

~~'''~~==Теорема~~'''~~ ==

<tex>3SAT \in NPC </tex>~~, ''т.е. задача о выполнимости булевой формулы в форме 3-КНФ <tex>NP</tex>-полна.''~~

~~----~~ ~~'''~~==Доказательство~~'''~~==

Для того, чтобы доказать <tex>NP</tex>-полноту задачи, необходимо установить следующие факты:

Анонимный участник

Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Служебная:Сравнение_версий/323»