素因数分解をSAT(充足可能性問題)に変換したいと思っています。
掛け算をCNFに変換しようと思ったのですが、やり方がよくわかりません。
そもそも素直に掛け算をCNFに変換するとXORが必要になって変換が多項式時間に収まらないような気がしています。
うまい変換方法はあるでしょうか。
素因数分解はNPに属するはずだからNP完全問題であるSATに多項式時間帰着できますよね?

質問者からの補足コメント

  • 素因数分解は素因数分解ですけど。
    なぜ定義なんか聞かれるんでしょう。
    いまは与えられた自然数を1でない2つの自然数の積の形に直すことを目標にします。

    No.1の回答に寄せられた補足コメントです。 補足日時:2015/03/18 07:35
  • 与えられた自然数nに対してn=abを満たすような1でない自然数a,bが存在するときYES,
    存在しないときNOを返してください。
    これっていちいち確認することですか?
    CNFの充足解が見つかったらa,bも特定できると嬉しいです。

      補足日時:2015/03/18 19:47
  • YESかNOかはPだけどa,bを求めるのはPかどうかわからないてことですか。
    排他的論理和で変数を増やせばいいってのはよくわからないです。
    あんまりうまい手が思いつかない。

    No.3の回答に寄せられた補足コメントです。 補足日時:2015/03/19 19:41
  • z=x xor yみたいですね。
    w xor x xor y xor zを表そうと思ったら
    a=w xor x
    b=a xor y
    c=b xor z
    みたいにやっていけばいいってことですか?
    確かに多項式サイズに収まりそうなような気がします。

      補足日時:2015/03/20 20:23
  • なるほど。だいぶ見えてきました。
    ありがとうございます。
    まだわからないことがでてくるかもしれないので質問はしばらく開けたままにして置かせてください。
    よろしくお願いします。

    No.6の回答に寄せられた補足コメントです。 補足日時:2015/03/21 00:44

このQ&Aに関連する最新のQ&A

A 回答 (6件)

そう, そんな感じ.



で, もともとの話に戻ると, 本質的には乗算ができればいいだけだから, 一度乗算回路を作っちゃう. そしてその回路からがんばって論理式に変換していく. このときに各素子の入出力関係を CNF で書いていく (xor については #5 の通り. and や or, not も同様に書き下しす) と, 最終的に回路全体を表す CNF は素子数の定数倍のサイズにおさまる.

k ビット同士の乗算だと回路の素子数が O(k^2) でいけるはず (and が k^2個と 2kビットくらいの加算器が k個くらい) だから, これで大丈夫.
この回答への補足あり
    • good
    • 0
この回答へのお礼

大筋は分かったんですけど実際、実装するとなると結構時間かかりそうです。
一旦この質問は閉じようと思います。
ありがとうございました。

お礼日時:2015/03/22 17:26

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 に対してどのような関数関係にあればいいでしょうか?
    • good
    • 0

ちなみに排他的論理和については新しい変数を導入するのが吉.

    • good
    • 0

私のところでは, 「与えられた自然数nに対してn=abを満たすような1でない自然数a,bが存在するときYES, 存在しないときNOを返してください」の意味で「素因数分解」ということはありえないんでねぇ....



そして「与えられた自然数nに対してn=abを満たすような1でない自然数a,bが存在するときYES, 存在しないときNOを返してください」は P だったはず.
この回答への補足あり
    • good
    • 0

その「素因数分解」に対してどのように YES/NO を返せばいいのですか?

    • good
    • 0

ん~....



「素因数分解はNPに属するはず」って, どういうことでしょうか? あなたのいう「素因数分解」とやらの定義を示してもらえますか?
この回答への補足あり
    • good
    • 0

このQ&Aに関連する人気のQ&A

お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!


人気Q&Aランキング