NP完全素因数分解をSATへ変換する

解決済

質問者：jogenara
質問日時：2015/03/17 21:05
回答数：6件

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

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

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
通報する

通報する

この質問への回答は締め切られました。

質問の本文を隠す

回答 (6件)

ベストアンサー優先
最新から表示
回答順に表示

No.6ベストアンサー

回答者： Tacosan
回答日時：2015/03/21 00:15

そう, そんな感じ.

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

k ビット同士の乗算だと回路の素子数が O(k^2) でいけるはず (and が k^2個と 2kビットくらいの加算器が k個くらい) だから, これで大丈夫.

- 0
- 件

通報する

この回答へのお礼

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

通報する

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

No.5

回答者： Tacosan
回答日時：2015/03/20 00:14

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