Изменения

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

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

6 байт добавлено, 17:37, 16 марта 2010
Нет описания правки
<tex>3SAT \in NPC </tex>, ''т.е. задача о выполнимости булевой формулы в форме 3-КНФ <tex>NP</tex>-полна.''
 
----
'''Доказательство'''
Анонимный участник
Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Служебная:Сравнение_версий/270»

Навигация