Изменения

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

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

27 байт добавлено, 19:38, 4 сентября 2022
м
rollbackEdits.php mass rollback
Таким образом, мы свели <tex>CNFSAT</tex> к <tex>3SAT</TEX>, следовательно <tex>3SAT \in NPH</tex>. Теорема доказана.
 
[[Категория:NP]]
Maintenance script
1632
правки
Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Служебная:Сравнение_версий/559...85708»

Навигация