素因数分解を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が見つからない時は、教えて!gooで質問しましょう!

このQ&Aを見た人が検索しているワード

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

Q素数の素因数分解

素数(例えば17)の素因数分解について
 (1)すでに素因数分解は終わっている (17の素因数分解は17)
 (2)素因数分解はできない
のどちらの見解が正しいですか?

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すばやく素因数分解する方法は?

「暗号解読」(サイモン・シン(著)青木薫(訳) 新潮社)という本を読んで、急に素数のことに関心を持ちました。

数十桁もある数(合成数)を素因数分解するのは、えらく時間がかかることが書かれていました。

中学生が計算する素因数分解や、「エラトステネスのふるい」のほかに、手計算や計算機を使って、合成数から素数を見つける方法(素因数分解)を知りたいので、ご存知の方教えてください。

できれば、計算機科学における現在、最速の素因数分解の方法(アルゴリズム)を知りたいです。

Aベストアンサー

確か、いまだはっきりした公式はできていないですよね?。
素因数分解。
いまあるアルゴリズムは、結局しらみつぶしに探し出す方法
でしかないと聞いたことがあります。

ちなみに、10進数の2000桁の素数を全て見つけ出そうとした場合、
全宇宙の全ての物質を現代の最速コンピュータの生産に
当てて並列処理を行ったとしても、宇宙の滅亡までに
計算が終了しないといわれています。

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

タイトル通りです.

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

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

Aベストアンサー

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

Q素因数分解について

X=√4,840,000 を素因数分解?? で解く場合、100*2*11=2,200
となると思いますが、素数の100を1000にしては駄目ですか?
そもそも、素因数分解のルールが理解出来ていません。
素因数分解の簡単なやり方を分かり易く教えて下さる方、宜しくお願いいたします。
因数分解は方程式なので、取っ付きにくいイメージがあります。

Aベストアンサー

素因数分解って、たとえば
12=2^2×3 って具合に、素数に分解すること。

で、それを応用してルートをはずす場合
ルートをはずすには数字の二乗であればいいわけだから、二乗の数を考えてみる。
√4840000の場合。
まず、真っ先に思いつくのは10000=100^2
(ここで、100を1000にすると1000^2=1000000となって計算できなくなる)
なので
4840000=484×100^2
今度は484に注目。
484は4(2^2)で割り切れるから
4840000=484×100^2
       =121×2^2×100^2
121は11^2だから

4840000=11^2×2^2×100^2
となるので

√4840000=√(11^2×2^2×100^2)
        =√(11×2×100)^2
        =11×2×100
        =2200

となる。

※a^2×b^2=(a×b)^2を利用しただけ。

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となります。

Q1を素因数分解しなさい

数学的には例外(素因数分解できない)は作りたくないのですが…。
でも、「1」の素因数分解と言われたら、答はどうなるのでしょう。

Aベストアンサー

普通には「1」でいいような気がします.
究極的には「2^0・3^0・5^0・…」(指数は全て 0) でしょうが.

QNPクラス、Pクラス、NP完全問題について教えてください

こんにちは。
授業でNPやPというような言葉が出てくるのですがいまいち理解できません。
あまり理解できていない用語はPクラス、NPクラス、P問題、NP問題、NP完全問題、NP完全、NP困難、判定問題などです。似たような言葉がいろいろ出てきてよく分からないです。これらの用語のうちで意味が同じようなものもあるのでしょうか?

自分なりに理解したことを書くと
Pクラスというのはその問題が現実的な時間内で解けて、NPクラスとは時間がかかりすぎて解けないというふうに理解しています。
NPクラスには最長パスを求めるアルゴリズムや大きな素数同士の積の因数分解などだと思います。ウィキペディアでも調べたのですが言葉が難しくて曖昧にしか分かりませんでした。
また、判定問題やハミルトン問題などについても知りたいです。何か良いサイトがありましたら紹介してもらえるとありがたいです。
ご回答よろしくお願いします。

Aベストアンサー

一番わかりにくい NP を中心に:
NP は Nondeterministic Polynomial の意味で, もともとは「非決定性チューリング機械によって多項式時間で判定できる」問題のクラスです. とはいわれても普通は「なんのこっちゃ」となるはずなので, もうちょっとわかりやすくいきましょう.
今は判定問題 (ある性質を持っているかどうかを答える問題) を考えているわけで, 普通は「与えられたもの」だけを使って答えることになります. これが「現実的な時間」=「多項式時間」でできるのが P.
これに対し, 「その性質を持っているときにはその証拠を示すことができる」という問題があります (もちろんその性質を持っていないときにはどんな「証拠」を持ってきてもダメ出しされる). このような問題のクラスを NP と呼びます.
例えばハミルトン閉路問題では, ハミルトン閉路を持つグラフに対しては「ああ, 確かに持っているね」と言わせるだけの証拠を示すことができます (具体的には「そのハミルトン閉路」そのものですが). 逆に, ハミルトン閉路を持たないグラフに対してはどんなものを持ってきても「ダメじゃん」と言われてしまいます. 従ってハミルトン閉路問題は NP に属します.
次に NP困難ですが, これは「NP に属するどの問題に対しても同等以上に難しい問題」のクラスです. でこの NP困難に属する問題のうち, NP にも属する問題を「NP完全問題」と呼びます. つまり NP困難問題は「NP に属する問題のうちで最も難しい問題」であるということになります.
で, クラスP は「『現実的な時間』=『多項式時間』で解ける問題」のクラスですがクラスNP は「時間がかかりすぎて解けない」ということではありません. P ⊂ NP なので, NP の中にも「簡単な問題」はあります.
あ~, 分からないところがあればどんどん指摘してください.

一番わかりにくい NP を中心に:
NP は Nondeterministic Polynomial の意味で, もともとは「非決定性チューリング機械によって多項式時間で判定できる」問題のクラスです. とはいわれても普通は「なんのこっちゃ」となるはずなので, もうちょっとわかりやすくいきましょう.
今は判定問題 (ある性質を持っているかどうかを答える問題) を考えているわけで, 普通は「与えられたもの」だけを使って答えることになります. これが「現実的な時間」=「多項式時間」でできるのが P.
これに対し, 「その性質を持ってい...続きを読む

Q2通りの素因数分解

素因数分解は一意に決まると学びましたが、大学時代にある数は2通りの素因数分解が出来ると聞いたような気がします。
私の記憶違いなのでしょうか?そんな数はあるのでしょうか?

Aベストアンサー

UFD=Unique factorization domain(一意分解整域,素元分解整域)と呼ばれる代数系においては、素因数分解は一意的です。整数環Zはユークリッド整域と呼ばれる環であるので、したがってPID(単項イデアル整域)であり、したがってまたUFDになるのです。ユークリッド整域のチェックは易しいので、この方法で素因数分解の一意性を示すのがひとつのテクニックです。

もちろんUFDではない環の元は、素因数分解は一意的にはできません。すなわち二通りの分解を持つ元が存在します。数というのを、たとえば整数Zの元だとか、そういう風に思うならば、ZはUFDだから素因数分解の一意性が破れる数は存在しない、ということになります。しかし、より拡張して、代数体の整数環の元という立場に立つならば、それが成り立たない例はいくらでも作れます。たとえばQ(√-5)の整数環を考えてみてください。Q(√-5)とは簡単に言うと、a+b√-5とかけるような複素数の集まりです。ただしa,bは有理数とします。この整数環と呼ばれる環の元6を考えます。これは2・3=(1+√-5)(1-√-5)と二通りの分解が可能です。そして、2,3,1+√-5,1-√-5はいずれもQ(√-5)における素数になっています。すなわち±1と±それ自身以外の約数をもたないので「素数」なのです。代数体における整数というのは、QにおけるZと同じような役割をする環だと思ってください。より詳しいことをお知りになりたければ、代数学の教科書なりなんなりを参照されたらと思います。

UFD=Unique factorization domain(一意分解整域,素元分解整域)と呼ばれる代数系においては、素因数分解は一意的です。整数環Zはユークリッド整域と呼ばれる環であるので、したがってPID(単項イデアル整域)であり、したがってまたUFDになるのです。ユークリッド整域のチェックは易しいので、この方法で素因数分解の一意性を示すのがひとつのテクニックです。

もちろんUFDではない環の元は、素因数分解は一意的にはできません。すなわち二通りの分解を持つ元が存在します。数というのを、たとえば整数Zの元だと...続きを読む

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ランキング

おすすめ情報