ド・モルガンの時間計算量について

質問

和積標準形（CNF）から積和標準形(DNF)に変換する際に、ド・モルガンの法則を適用すれば可能ですが、このときの時間計算量を教えてください。多項式時間でしょうか？それとも指数時間かかるのでしょうか？よろしければ、その理由も教えてください。

回答No.3

Tacosan

いや, 本当は「変換のための時間はどれだけか」を考えるためには「どのように表現するか」を決めないとダメなんだけどね.... ただ, ここでは「リテラルの変換 (x1 ⇔ !x1)」「和から積への変換」「積から和への変換」の 3つしかありません. しかも, どの変換を使うかは一意に決まりますし一旦変換してしまったら「前に戻ってもう一度変換し直し」のようなことはほぼ明らかに存在しないので, 「線形時間」とまで言い切ってよいと思います.
ちなみに裏技:
(!x1 x2) + (!x2 !x3 x4)
と
(x1 !x2) + (x2 x3 !x4)
は恒真かどうかという意味において等価です. で, CNF (x1 + !x2) (x2 + x3 + !x4) を { { x1, !x2 }, { x2, x3, !x4 } } という集合で表すと仮定する (この方法自体はよくある) と, これは DNF (x1 !x2) + (x2 x3 !x4) を表すと「解釈する」こともできます. だから, 「実は何もしなくていい」という考え方もできます.

回答No.2

Tacosan

以下 ! は否定ね.
つまり, CNF (x1 + !x2) (x2 + x3 + !x4) を DNF (!x1 x2) + (!x2 !x3 x4) に変換したい, ということ?
明らかに多項式時間, もっといえば線形時間ですね.

お礼

理解頂きありがとうございます。そういうことです。准教授に聞いても本当に多項式時間なの？と逆に聞き返され答えることができませんでした。よろしければ、なぜ明らかに多項式時間なのか教えてください。ちなみにネットや書物を調べたのですがド・モルガンの時間計算量は載っていませんでした。もしそのようなことが載っているネットや書物も知っているならば、教えていただければ幸いです。

回答No.1

Tacosan

ド・モルガン?
どういうことをしたいのか, 簡単な具体例で書いてもらえませんか?

お礼

返答ありがとうございます。どういうことをしたいのかというと、SAT（充足可能性問題）をDNFの恒真判定問題に多項式時間帰着したいのですが、入力の変換にド・モルガンの法則を適用したいのです。これでわかるでしょうか？文章が下手ですいません。