Полиномиальные сводимости и NP-полные задачи. Классы NP, coNP, NPC/Задачи/Tautology in coNP — различия между версиями
Материал из DISCOPAL
StasFomin (обсуждение | вклад) |
Abondar (обсуждение | вклад) |
||
Строка 7: | Строка 7: | ||
Покажите, что эта задача в coNP. | Покажите, что эта задача в coNP. | ||
− | [[Category: | + | Для того, что бы доказать, что указанная выше задача в coNP, достаточно доказать то, что задача "Правда ли, что существует набор переменных, такой что ДНФ ложна?" является NP задачей. |
+ | При этом необходимо понимать, что ДНФ можно преобразовать в отрицание КНФ, и задача приобретает вид "Правда ли, что существует такой набор переменных, что КНФ истинна?". Но эта задача | ||
+ | является NP. | ||
+ | |||
+ | [[Category:На проверку]] | ||
<!--Вообще-то, решения уже есть--> | <!--Вообще-то, решения уже есть--> |
Версия 12:24, 24 ноября 2014
Tautology in coNP
Правда ли, что ДНФ истинна для всех присваниваний?
Покажите, что эта задача в coNP.
Для того, что бы доказать, что указанная выше задача в coNP, достаточно доказать то, что задача "Правда ли, что существует набор переменных, такой что ДНФ ложна?" является NP задачей. При этом необходимо понимать, что ДНФ можно преобразовать в отрицание КНФ, и задача приобретает вид "Правда ли, что существует такой набор переменных, что КНФ истинна?". Но эта задача является NP.