No.6ベストアンサー
- 回答日時:
そう, そんな感じ.
で, もともとの話に戻ると, 本質的には乗算ができればいいだけだから, 一度乗算回路を作っちゃう. そしてその回路からがんばって論理式に変換していく. このときに各素子の入出力関係を CNF で書いていく (xor については #5 の通り. and や or, not も同様に書き下しす) と, 最終的に回路全体を表す CNF は素子数の定数倍のサイズにおさまる.
k ビット同士の乗算だと回路の素子数が O(k^2) でいけるはず (and が k^2個と 2kビットくらいの加算器が k個くらい) だから, これで大丈夫.
この回答へのお礼
お礼日時:2015/03/22 17:26
大筋は分かったんですけど実際、実装するとなると結構時間かかりそうです。
一旦この質問は閉じようと思います。
ありがとうございました。
No.5
- 回答日時:
P とか NP とかいったクラスは, もともと「YES か NO かを答える」判定問題を対象としています. それに対して「N = ab となる a (や b) を求める」ってのは「YES か NO かを答える」問題じゃないから, 本来は P だの NP だのといったクラスとは関係ないんです.
これが, 例えば「N と k が与えられたときに, N が k 以下の因数を持つかどうか」という問題であれば「YES か NO かを答える」問題になるので P なり NP なりといったクラスのどこかに入るはずです.
あと, 排他的論理和で「変数を増やす」ってのは, 次の CNF 式を考えてみてください:
(not x or not y or not z) and (not x or y or z) and (x or not y or z) and (x or y or not z)
この 4つを全て真にするためには, z は x と y に対してどのような関数関係にあればいいでしょうか?
No.3
- 回答日時:
私のところでは, 「与えられた自然数nに対してn=abを満たすような1でない自然数a,bが存在するときYES, 存在しないときNOを返してください」の意味で「素因数分解」ということはありえないんでねぇ....
そして「与えられた自然数nに対してn=abを満たすような1でない自然数a,bが存在するときYES, 存在しないときNOを返してください」は P だったはず.
お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!
おすすめ情報
- ・漫画をレンタルでお得に読める!
- ・14歳の自分に衝撃の事実を告げてください
- ・架空の映画のネタバレレビュー
- ・「お昼の放送」の思い出
- ・昨日見た夢を教えて下さい
- ・【お題】絵本のタイトル
- ・【大喜利】世界最古のコンビニについて知ってる事を教えてください【投稿~10/10(木)】
- ・メモのコツを教えてください!
- ・CDの保有枚数を教えてください
- ・ホテルを選ぶとき、これだけは譲れない条件TOP3は?
- ・家・車以外で、人生で一番奮発した買い物
- ・人生最悪の忘れ物
- ・【コナン30周年】嘘でしょ!?と思った○○周年を教えて【ハルヒ20周年】
- ・ハマっている「お菓子」を教えて!
- ・最近、いつ泣きましたか?
- ・夏が終わったと感じる瞬間って、どんな時?
- ・10秒目をつむったら…
- ・人生のプチ美学を教えてください!!
- ・あなたの習慣について教えてください!!
- ・牛、豚、鶏、どれか一つ食べられなくなるとしたら?
- ・都道府県穴埋めゲーム
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
-
50以下は“50”も入るのですか?
-
5進法を10進法への直し方
-
16進小数0.Cを10進数小数に変換...
-
dBm/HzからdBm/MHzへの単位変換
-
偏微分の記号をタイプするため...
-
8進数から16進数 16進数から8進数
-
2進数の0.101101101101・・・...
-
10進数の50を2進数で表すといく...
-
Excelにて、時間(8:30等)を数...
-
線形代数 直交行列 回転行列
-
HEX2BIN関数の使い方。
-
Excel 16進数
-
2進数の1010は、10進数ではいく...
-
算数計算 大至急お願いします
-
フーリエ変換・逆変換の虚数成...
-
ACアダプターの消費電力の件
-
単位の変換(立方メートルをc...
-
=(イコール)の上下に点々があ...
-
ヤコビアンが0になってしまう場...
-
10進数を5進数に変換する式
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
-
50以下は“50”も入るのですか?
-
5進法を10進法への直し方
-
16進小数0.Cを10進数小数に変換...
-
HEX2BIN関数の使い方。
-
Excel 16進数
-
dBm/HzからdBm/MHzへの単位変換
-
偏微分の記号をタイプするため...
-
10進数の50を2進数で表すといく...
-
dBm→dBμV/mの換算について
-
小数点が混じった2進数を8進数...
-
EXCELで10進数表記をB...
-
10進数25.25を2進数に変換する...
-
.7進数2654を4進数に変換した...
-
ヤコビアンが0になってしまう場...
-
8進数から16進数 16進数から8進数
-
2進数の1010は、10進数ではいく...
-
=(イコール)の上下に点々があ...
-
幾何と代数は同じ数学でしょうか
-
1.6dLは、何L何dLですか? 問題...
-
16進数の1Cを二進数と十進数で...
おすすめ情報
素因数分解は素因数分解ですけど。
なぜ定義なんか聞かれるんでしょう。
いまは与えられた自然数を1でない2つの自然数の積の形に直すことを目標にします。
与えられた自然数nに対してn=abを満たすような1でない自然数a,bが存在するときYES,
存在しないときNOを返してください。
これっていちいち確認することですか?
CNFの充足解が見つかったらa,bも特定できると嬉しいです。
YESかNOかはPだけどa,bを求めるのはPかどうかわからないてことですか。
排他的論理和で変数を増やせばいいってのはよくわからないです。
あんまりうまい手が思いつかない。
z=x xor yみたいですね。
w xor x xor y xor zを表そうと思ったら
a=w xor x
b=a xor y
c=b xor z
みたいにやっていけばいいってことですか?
確かに多項式サイズに収まりそうなような気がします。
なるほど。だいぶ見えてきました。
ありがとうございます。
まだわからないことがでてくるかもしれないので質問はしばらく開けたままにして置かせてください。
よろしくお願いします。