No.6ベストアンサー
- 回答日時:
いや, AKS を使っていいなら「NP には含まれる」のはほとんど明らかなんだってばぁ>#5.
そりゃまあ NP に属してかつ NP困難ってことはありえるけど....
No.7
- 回答日時:
No.6さん
NPの定義は「yes となる証拠が与えられたとき、その証拠が本当に正しいかどうかを多項式時間で判定できる問題。」
https://ja.wikipedia.org/wiki/NP
ということなので、当該の問題がNPに属するかどうかは私には分かりませんが
結局全部調べるしかないのでは?
No.4
- 回答日時:
素数判定がPに属することはAKS素数判定法で示されてますよね
https://ja.wikipedia.org/wiki/AKS%E7%B4%A0%E6%95 …
さて、「a以上b以下の範囲に素数が存在するか」のオーダーは
O(aの桁数の多項式)+O(a+1の桁数の多項式)+・・・+O(bの桁数の多項式)
≦(b-a+1)O(bの桁数の多項式)
=O(exp(bの桁数))xO(bの桁数の多項式)
=O(exp(bの桁数))
なので、NPには入るんじゃないですかね
No.3
- 回答日時:
素数であることの判定が NP に属することは, 例えば
https://en.wikipedia.org/wiki/Primality_certific …
にある. 多少めんどうだけど基本的には Fermat テストっぽぃ.
この回答へのお礼
お礼日時:2016/02/06 18:54
回答ありがとうございます。
うう、英語ですか。
これを読むのはちょっとしんどいです。
すいません。
充足可能性問題に帰着するのもかなり大変そうですね。
お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!
おすすめ情報
- ・漫画をレンタルでお得に読める!
- ・人生のプチ美学を教えてください!!
- ・10秒目をつむったら…
- ・あなたの習慣について教えてください!!
- ・牛、豚、鶏、どれか一つ食べられなくなるとしたら?
- ・【大喜利】【投稿~9/18】 おとぎ話『桃太郎』の知られざるエピソード
- ・街中で見かけて「グッときた人」の思い出
- ・「一気に最後まで読んだ」本、教えて下さい!
- ・幼稚園時代「何組」でしたか?
- ・激凹みから立ち直る方法
- ・1つだけ過去を変えられるとしたら?
- ・【あるあるbot連動企画】あるあるbotに投稿したけど採用されなかったあるある募集
- ・【あるあるbot連動企画】フォロワー20万人のアカウントであなたのあるあるを披露してみませんか?
- ・映画のエンドロール観る派?観ない派?
- ・海外旅行から帰ってきたら、まず何を食べる?
- ・誕生日にもらった意外なもの
- ・天使と悪魔選手権
- ・ちょっと先の未来クイズ第2問
- ・【大喜利】【投稿~9/7】 ロボットの住む世界で流行ってる罰ゲームとは?
- ・推しミネラルウォーターはありますか?
- ・都道府県穴埋めゲーム
- ・この人頭いいなと思ったエピソード
- ・準・究極の選択
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
-
(x-1)(x-2)(x-3)の展開の...
-
約数と因数の違い(∈N)
-
単項式も整式と言うのですか。
-
多項式について質問です。 エク...
-
中学生です。この数学の問題に...
-
部分空間であることの証明
-
陪微分とは何ですか?
-
数学 有理式 無理式
-
フルビッツの安定判別法
-
単項式と分数式の違いについて
-
arcsinのマクローリン展開について
-
三角関数系が直交性を持つとい...
-
ラグランジュ補間についてです...
-
素イデアルの判定がわからないです
-
2はZ[x]の既約元ですか?
-
ド忘れしたんですけど、2分の1...
-
xが分子の足し算、どうやるんで...
-
2.5みたいな数字を分数になおす...
-
2は5で割り切れません。 あまり...
-
小学校4年生の算数の教科書で...
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
おすすめ情報
もう回答も出尽くした感じでしょうか。
そろそろ質問を〆ようかとおもいますが、結論としては
1.素数探索はNPに入る。
2.充足可能性問題に帰着するのはかなり難しい。
ということでよろしいでしょうか。