素因数分解を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を見た人が検索しているワード

このQ&Aと関連する良く見られている質問

QNP完全 素因数分解をSATに変換するから派生 2進数の大小関係について

以前「NP完全 素因数分解をSATに変換する」という質問をしたものです。
素因数分解をCNFに変換するスクリプトが出来たのですが、
a*b=cという関係だけだとa<=bのときもa>bの時も解になってしまいます。
できれば片方(a>b)は解じゃなくしたいと思っています。
aがnビット二進数[a_(n-1),a_(n-2),...,a_1,a_0]
bがnビット二進数[b_(n-1),b_(n-2),...,b_1,b_0]
で与えられているとき、
a<=bという条件はどのようにCNFに変換すればよいでしょうか。
CNFのサイズが元の式の多項式倍におさまると嬉しいです。
よろしくお願いします。

Aベストアンサー

記号として x≡y は「x と y が同じ値のとき真, そうでなければ偽」ということにする.

ポイントは
(※) z ≡ f(x, y) という式が x, y, z の CNF で書ける
ことにある (f(x, y) = x || y などで試してみるといい).

これがわかれば, あとは
各演算に対して変数を割り当てる
ことで終わる.

具体的にちょっとだけやると, まず最初はその長い式を z とおいて
その長い式が真であることと論理式 z && (z ≡ その長い式) が充足可能であることが等価
ということから後者の式を使う. このうち z はもういいので残った「z ≡ その長い式」の部分を分解していく.

ここで, その長い式は全体として (a4<b4) || (なんか) という形なので
x[0] = a4<b4, x[1] = (なんか)
とおくと
z && (z ≡ その長い式) が充足可能であることと z && [(z ≡ (x[0] || x[1])) && (x[0] ≡ (a4<b4)) && (x[1] ≡ (なんか))] が充足可能であることとは等価
である. ここで z ≡ (x[0] || x[1]) や x[0] ≡ (a4<b4) は (※) から CNF で書けるので, 残った
x[1] ≡ (なんか)
の部分を分解して CNF で書けばいい. そしてそれはここでやったことを繰り返していくだけである.

記号として x≡y は「x と y が同じ値のとき真, そうでなければ偽」ということにする.

ポイントは
(※) z ≡ f(x, y) という式が x, y, z の CNF で書ける
ことにある (f(x, y) = x || y などで試してみるといい).

これがわかれば, あとは
各演算に対して変数を割り当てる
ことで終わる.

具体的にちょっとだけやると, まず最初はその長い式を z とおいて
その長い式が真であることと論理式 z && (z ≡ その長い式) が充足可能であることが等価
ということから後者の式を使う. このうち z はもういいので残った「z ≡...続きを読む

Q自然数nを素因数分解すると、素因数は2と3であり、それ以外の素因数はない。また、nの正の約数の個数は

自然数nを素因数分解すると、素因数は2と3であり、それ以外の素因数はない。また、nの正の約数の個数はちょうど12である。このような自然数nをすべて求めよ。
わかる方教えてください!

Aベストアンサー

n=2^a×3^bと表せます。^aはa乗を示します。
abはそれぞれ自然数です。
ここで約数の数は(a+1)×(b+1)=12と表せます。
これは(a=1,b=5)(a=2,b=3)(a=3,b=2)(a=5,b=1)の4通りです。
それぞれnを求めると、486,108,72,96となります。

Q素因数分解は,NP完全問題でしょうか?

タイトル通りです.

素因数分解はNP完全問題でしょうか? それとも,クラスNPに属するだけでしょうか?

ド素人ですのでできるだけ解り易くお願いいたします・・・.

Aベストアンサー

http://www.cs.gunma-u.ac.jp/~nakano/Algo/npc.html
をご覧ください。

Q素因数分解の答え方について

この前数学技能検定(数検)を受けてきたのですが、2009を素因数分解しろという問題が出て、私は、7×7×41という答え方をしてしまったと思うのですが、やはり7の二乗×41と書かないとバツになってしまいますかね?
どう思いますか?回答よろしくお願いします。

Aベストアンサー

数検を受けたことがないのですが、普通累乗を用いますね。バツかどうかはわかりませんが、5aと答えるところをa×5と書いているようなものでしょうね。

Q素因数分解の問題について

高校の数学の問題なのですが、
3^240-1を素因数分解したとき2は何回現れるか、という問題があって
どうしても解き方が分かりません。
皆さんの力をお貸しください。よろしくお願いします。

Aベストアンサー

とりあえず、
3^240-1=(3^120+1)(3^120-1)=(3^120+1)(3^60+1)(3^60-1)
=・・・=(3^120+1)(3^60+1)(3^30+1)(3^15+1)(3^15-1)
と分解する。
ここで、3のべき乗に関し、3の奇数乗は4で割ると3余り、3の偶数乗
は4で割ると1余る、ということを使う。(これは帰納的に簡単に
分かるでしょう。)
これより、3の偶数乗+1は4で割ると2余る。つまり、3の偶数乗+1は
2では割り切れるが、4では割り切れず、したがって、素因数2を一つ
だけ持つ。
よって、3^240+1、3^60+1、3^30+1はそれぞれ、素因数2を一つだけ
もつ。
また、3の15乗については、公式、
x^3+1=(x+1)(x^2-x+1)
x^3-1=(x-1)(x^2+x+1)
を使って分解するとよい。
そして、同じように、4で割ったときの余りを考えるとよい。
割り切れなければ、2では1回しか割り切れない・・・


人気Q&Aランキング

おすすめ情報