Изменения

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

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

64 байта добавлено, 14:51, 17 марта 2010
→‎Доказательство
== Доказательство ==
Для доказательства теоремы необходимо установить два факта:
* <tex> CNFSAT /\in NP </tex>* <tex> CNFSAT \in NPH </tex>=== Доказательство <tex> CNFSAT \in NPH NP </tex>===
Анонимный участник
Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Служебная:Сравнение_версий/311»

Навигация