Конвертация DNF в CNF: легкий или жесткий

Относительно потока, Доказывающего, что преобразование из CNF в DNF является NP-Hard (и связанный математический поток ):

Как насчет другого направления, от DNF до CNF? Это легко или сложно?

На странице 2 этой статьи они, похоже, намекают на то, что оба направления одинаково трудны, когда говорят: « Мы заинтересованы в максимальном увеличении размера при переключении с представления CNF на представление DNF (или наоборот) ».

Но DNF-SAT находится в P, а CNF-SAT является NP- полной. Поэтому, учитывая выражение DNF , должно быть равнозначное выражение CNF , длина которого полиномиальна по длине . И преобразование может быть сделано за время poly. Это правильно? $\phi_1$ $\phi_2$ $\phi_1$ $\phi_1 \to \phi_2$

Редактировать: изменен эквивалент на равноудаленный (то есть дополнительные переменные разрешены в ). $\phi_2$

complexity-theory logic satisfiability normal-forms Мартин Сеймур
источник

Вы можете перейти от любой формулы к CNF, которая выполнима точно, когда исходная формула находится в полиномиальном времени. Вот почему CNF-SAT является NP-полной. Любой экземпляр SAT (NP-полная проблема) может быть уменьшен до CNF-SAT за полиномиальное время. Я думаю, что именно его перевод, а не просто сохранение удовлетворенности, всегда может привести к экспоненциальному взрыву, но я не могу сказать это точно.

Джейк

См. En.wikipedia.org/wiki/Tseitin_transformation . По сути, если вы разрешите введение вспомогательных переменных, вы можете выполнить это преобразование за многократное время (увеличив размер формулы максимально линейно).

jschnei

Вам нужно решить, хотите ли вы разрешить преобразованию вводить новые переменные или преобразованная формула должна ссылаться на тот же набор переменных (без новых переменных). Это тонкий момент, который сильно влияет на ответ. Итак, о чем вы хотите спросить?

@ Джейк Вы можете перейти от любой формулы к равноудаленному CNF, потому что CNF-SAT является NP-полным. Не совсем «почему» CNF-SAT является NP-полной: обычное доказательство того, что CNF-SAT является NP-полной, не предполагает перевода произвольных формул в CNF; скорее это переводит машины Тьюринга в формулы CNF.

Дэвид Ричерби

Для DW и других - я имел в виду уравнительную неудовлетворенность . В этом смысле кажется, что условная эквивалентность - это просто сокращение (в данном случае, к другой булевой формуле).

Мартин Сеймур

Ответы:

Если вы хотите ввести дополнительные переменные, вы можете преобразовать форму DNF в форму CNF за полиномиальное время с помощью преобразования Цейтин . Полученная формула CNF будет равнозначна исходной формуле DNF: формула CNF будет выполнимой, если и только если исходная формула DNF была выполнимой. Смотрите также https://en.wikipedia.org/wiki/Conjunctive_normal_form#Conversion_into_CNF .

Если вы не хотите разрешать ввод дополнительных переменных, преобразование из DNF в форму CNF сопряжено с NP. В частности, проверка того, является ли формула DNF тавтологией, сопро-сложна. Однако проверка того, является ли формула CNF тавтологией, может быть выполнена за полиномиальное время (вы просто отдельно проверяете, является ли каждое предложение тавтологией, что легко, поскольку каждое предложение является дизъюнкцией литералов). Поэтому, если бы вы могли преобразовать форму DNF в форму CNF за полиномиальное время, не вводя новые переменные, вы бы получили алгоритм полиномиального времени для проверки того, является ли формула DNF тавтологией, что кажется маловероятным, учитывая, что мы ожидаем P не равно co-NP. Или, другими словами, преобразование из DNF в форму CNF без введения дополнительных переменных является сопро-сложным.

Это разница между эквивалентностью против equisatisfiability . Эквивалентность требует, чтобы две формулы имели одинаковый набор решений (и, следовательно, не позволяют вводить дополнительные переменные). Уравновешенность требует только того, чтобы обе формулы были выполнимыми или обе были неудовлетворительными (и, следовательно, позволяли вводить дополнительные переменные).

DW
источник

@ Mehrdad, пожалуйста, не используйте комментарии, чтобы задавать новые вопросы. У нас есть «Задать вопрос» в правом верхнем углу, если у вас есть новый вопрос, который вы хотите задать. Но, просто небольшой совет ... вы можете прочитать вопрос в верхней части этой страницы, прежде чем задавать новый вопрос ... или, в этом отношении, опубликовать этот комментарий. Я не могу не заметить, что вы задали вопрос, где ответ находится на той же странице, что и ваш вопрос.

@DW: Ой, я действительно видел другой пост немного позже и забыл удалить свой комментарий здесь, извините. Убрал это сейчас.

user541686