Изменения

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

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

70 байт добавлено, 18:57, 19 марта 2010
Нет описания правки
== Теорема ==
<tex> CNFSAT \in NPC. </tex>, то есть задача <tex> CNFSAT </tex> - [[NP-полная]].
== Доказательство ==
Для доказательства теоремы необходимо установить два факта:
Анонимный участник
Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Служебная:Сравнение_версий/545»

Навигация