素数探索はＮＰ？

「a以上b以下の範囲に素数が存在するか」
という問題はNPに入りますか？
入るとしたらどのように充足可能性問題に帰着できますか？

素数判定はＰに入るらしいですが難しい理論が必要らしいです。
できればあんまり難しい理論は使わないでくれるとありがたいです。

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

• もう回答も出尽くした感じでしょうか。
  そろそろ質問を〆ようかとおもいますが、結論としては
  
  １．素数探索はＮＰに入る。
  ２．充足可能性問題に帰着するのはかなり難しい。
  
  ということでよろしいでしょうか。

    補足日時：2016/02/16 00:00

No.6 ベストアンサー 回答者： Tacosan 回答日時： 2016/02/09 23:32

いや, AKS を使っていいなら「NP には含まれる」のはほとんど明らかなんだってばぁ＞#5.

そりゃまあ NP に属してかつ NP困難ってことはありえるけど....

No.7 回答者： ibm_111 回答日時： 2016/02/11 23:50

No.6さん

NPの定義は「yes となる証拠が与えられたとき、その証拠が本当に正しいかどうかを多項式時間で判定できる問題。」
https://ja.wikipedia.org/wiki/NP
ということなので、当該の問題がNPに属するかどうかは私には分かりませんが
結局全部調べるしかないのでは？

No.5 回答者： ibm_111 回答日時： 2016/02/09 06:32

なるほど、NPではなくてNP困難かもしれないですね

No.4 回答者： ibm_111 回答日時： 2016/02/06 12:57

素数判定が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には入るんじゃないですかね

この回答へのお礼

回答ありがとうございます。
結論がO(exp(bの桁数))じゃNPにならないんじゃないでしょうか。

お礼日時：2016/02/06 18:55

No.3 回答者： Tacosan 回答日時： 2016/02/06 02:44

素数であることの判定が NP に属することは, 例えば

https://en.wikipedia.org/wiki/Primality_certific …
にある. 多少めんどうだけど基本的には Fermat テストっぽぃ.

この回答へのお礼

回答ありがとうございます。
うう、英語ですか。
これを読むのはちょっとしんどいです。
すいません。
充足可能性問題に帰着するのもかなり大変そうですね。

お礼日時：2016/02/06 18:54

No.2 回答者： Tacosan 回答日時： 2016/02/06 00:33

a以上b以下の整数を全部非決定性に並べておいて, それが素数かどうか調べればいいだけだから NP であることは一瞬でわかるんだけど

ね....

この回答へのお礼

回答ありがとうございます。
素数であることの多項式サイズの証拠をどうすればいいか悩みました。
素数判定はＰだから多項式サイズの証拠はあるんだと思いますが、やっぱり難しい理論が必要？

お礼日時：2016/02/06 01:06

No.1 回答者： ngkdddjkk 回答日時： 2016/02/05 23:24

リーマン予想が定理になればPになるかと。

(素数定理でリーマン予想が解決すれば素数の順番が確か決定可能であったはず)

この回答へのお礼

解答ありがとうございます。
素数定理、、、リーマン予想、、、やっぱり難しい理論が必要ですか？
現時点ではＮＰに入るかどうかもわからないですか？

お礼日時：2016/02/05 23:42