Доказательство того, что преобразование из CNF в DNF является NP-Hard

20

Как я могу доказать, что преобразование из CNF в DNF является NP-Hard?

Я не прошу ответа, просто несколько советов о том, как это доказать.

complexity-theory np-hard satisfiability sat-solvers normal-forms jkjk
источник
5
Для более глубокого анализа взгляните на эту статью «О преобразовании CNF в DNF»
Vor
@ A.Schulz: оригинальное определение в статье Стива Кука определяет его, используя сокращения Кука. Похоже, что это сокращение используется при обсуждении общей NP-твердости en.wikipedia.org/wiki/NP-hard
Kaveh
Преобразование CNF <-> DNF не является решением, для него необходим язык. это скорее функция с входом и выходом, и она должна быть преобразована в задачу решения, чтобы спросить, не находится ли она в NP и т. д., что доказано, что проблема, не связанная с решением, ведет к экспоненциальному увеличению размера [например, в Vors ref], поэтому NP-полная версия решения проблемы [если она есть], вероятно, является существенным упрощением. также, как показывает Vors, фактическая сложность преобразования CNF <-> DNF является активной исследовательской проблемой ... обратите внимание, что есть некоторое сходство с эффективностью алгоритма сжатия ...
vzn
2
@vzn Вопрос спрашивает, является ли NP- жесткий, а не NP- Complete. Это означает, что членство в NP не требуется, поэтому это не должно быть проблемой решения.
Дэвид Ричерби

Ответы:

18

Неофициально:

В DNF вы можете выбрать любое предложение как истинное, чтобы сделать формулу истинной. Это означает, что DNF, который эквивалентен некоторому CNF, является в основном перечислением всех решений логического сата на CNF. Обратите внимание, что может быть экспоненциальное количество решений. Поскольку решение логического сбоя для CNF для одного решения является NP-полным, преобразование в DNF, по сути, означает решение для каждого решения. Так что это, по крайней мере, так же сложно, как Boolean SAT, и, следовательно, NP-hard.

Реал Слав
источник