Обсуждение:Конъюнктивная нормальная форма

Автору текста:

В теории вычислительной сложности важную роль играет задача выполнимости булевых формул в конъюнктивной нормальной форме. Эта задача NP-полна, и она сводится к задаче 3-SAT, которая в свою очередь сводится ко многим другим NP-полным задачам.

""

Вопрос1: а какую вычислительную сложность имеет задача выполнимости ДИЗЪЮНКТИВНОЙ нормальной формы?
Вопрос2: какую вычислительную сложность имеет задача перехода от КНФ к ДНФ? и наоборот? — Эта реплика добавлена с IP 213.148.186.137 (о)

1. Линейную, так как можно независимо проверять каждое слагаемое в ДНФ.
2. Для КНФ с n конъюнкциями, эквивалентная ДНФ может содержать экспоненциальное от n число дизъюнкций, так что сложность экспоненциальна. Пример: ДНФ для (x1 | y1) & (x2 | y2) & ... & (xn | yn) содержит $2^{n}$ дизъюнктов. -- X7q 22:33, 19 ноября 2009 (UTC)

Вставленый материал

Участник:Peni, я, конечно, не специалист, но где аргументы по удалению? --Не А 12:50, 22 августа 2007 (UTC)

Надо бы пример поменять.

Господа, ведь приведённый пример КНФ упрощается до !x
Это видно и невооружённым глазом, и подтверждается Mathematicой

Ixanezis 21:18, 14 июня 2012 (UTC)