Изменения

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

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

16 байт добавлено, 19:02, 19 марта 2010

→‎Теорема

== Теорема ==

<tex> CNFSAT \in NPC </tex>, то есть задача принадлежит классу [[NP-полнота|NP-полных]] задач.

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

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

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