A 回答 (3件)
- 最新から表示
- 回答順に表示
No.3
- 回答日時:
いや, 本当は「変換のための時間はどれだけか」を考えるためには「どのように表現するか」を決めないとダメなんだけどね.... ただ, ここでは「リテラルの変換 (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
- 回答日時:
以下 ! は否定ね.
つまり, CNF (x1 + !x2) (x2 + x3 + !x4) を DNF (!x1 x2) + (!x2 !x3 x4) に変換したい, ということ?
明らかに多項式時間, もっといえば線形時間ですね.
理解頂きありがとうございます。そういうことです。准教授に聞いても本当に多項式時間なの?と逆に聞き返され答えることができませんでした。よろしければ、なぜ明らかに多項式時間なのか教えてください。ちなみにネットや書物を調べたのですがド・モルガンの時間計算量は載っていませんでした。もしそのようなことが載っているネットや書物も知っているならば、教えていただければ幸いです。
お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!
似たような質問が見つかりました
- 統計学 統計学の問題です!急ぎです 1 2023/02/08 13:51
- 統計学 以下の問題が分からないので計算式を教えてください ある企業が製造している電球の寿命の母平均と,母標準 3 2023/01/14 00:43
- 数学 線形代数 正則 階数 3 2023/03/22 07:52
- 物理学 ビオサバールの法則で円弧部分から座標(x,0,0)に対する磁束密度を計算したいのですがここで詰まって 1 2023/04/30 13:09
- Excel(エクセル) 電卓は正しいのに エクセルで計算させると間違った答えです。なぜ? 7 2022/08/11 07:04
- 統計学 統計学の質問【帰無仮説】 大学で、現在の在籍者の平均通学時間が60分であるという帰無仮説を、それが6 8 2023/05/23 20:56
- Excel(エクセル) 月間シフト表から総勤務時間を計算する関数 4 2023/05/20 07:12
- 統計学 t分布導出時のヤコビ行列式について教えて下さい。 1 2022/07/04 21:36
- 物理学 アインシュタイン博士の相対性理論は間違っていたのでしょうか? 6 2022/04/13 17:36
- 統計学 不偏分散を計算するときに標準偏差和をn-1で割りますが、なぜ-1なのでしょうか? 「なぜnでなくn- 5 2022/07/04 14:54
おすすめ情報
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
-
50以下は“50”も入るのですか?
-
16進小数0.Cを10進数小数に変換...
-
5進法を10進法への直し方
-
HEX2BIN関数の使い方。
-
8進数から16進数 16進数から8進数
-
access アクセス 例:11:45 ...
-
小数点が混じった2進数を8進数...
-
偏微分の記号をタイプするため...
-
数学の問題で
-
平行の記号
-
ド・モルガンの時間計算量について
-
Excel 16進数
-
16進数の1Cを二進数と十進数で...
-
EXCELで10進数表記をB...
-
2進数の小数を10進数に変換...
-
マイナスの進数変換
-
自然対数の単調変換について
-
10進数→2進数への変換が理解...
-
幾何と代数は同じ数学でしょうか
-
2進数の0.101101101101・・・...
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
-
50以下は“50”も入るのですか?
-
5進法を10進法への直し方
-
16進小数0.Cを10進数小数に変換...
-
HEX2BIN関数の使い方。
-
Excel 16進数
-
10進数の50を2進数で表すといく...
-
偏微分の記号をタイプするため...
-
dBm/HzからdBm/MHzへの単位変換
-
dBm→dBμV/mの換算について
-
8進数から16進数 16進数から8進数
-
CASLII:文字列→数字への変換の...
-
EXCELで10進数表記をB...
-
算数計算 大至急お願いします
-
ヤコビアン(関数行列式)につ...
-
ACアダプターの消費電力の件
-
=(イコール)の上下に点々があ...
-
フーリエ変換・逆変換の虚数成...
-
n進法→m進法への変換
-
2進数の0.101101101101・・・...
-
小学4年生の算数(小数)の問題で...
おすすめ情報