「素数判定アルゴリズムを開発」記事へのコメント

素因数分解もＰに入っている

[Anonymous Coward]

と専門家は思っているらしい。（今回の件に関するニュースでどこかで読んだ）

量子コンピュータでできちゃうし、本物のＮＰハードよりは少し簡単だという感じがあるのだろうか。

専門家の方、そのあたりの雰囲気はどうなんですか？

素因数分解はＰに入っていない（と思う）

[the Poster (3856)]

一応専門家の端くれですが、少なくとも私の周りでは
素因数分解はPではないと思われています。
でも、NP-complete（決定問題の場合ね）でもないと思われています。
じゃあ結局どこに入るのだといいますと、その中間のクラス。

P

Re:素因数分解はＰに入っていない（と思う）

[Anonymous Coward]

P≠NP　が成立するならば、その中間クラスが存在することがすぐに言えますので

これって，「P ≠ NP∩coNP がすぐに言える」ってことですか？

Re:素因数分解はＰに入っていない（と思う）

[tix (7637)]

P≠NP の仮定の下で、 P でもなく NP 完全でもないような NP 問題があることは示せます。が、同じ仮定の下で P≠NP∩coNP が言えるかどうかは知りません。少し調べた感じでは、そういう結果は得られていなさそうです。

--
鵜呑みにしてみる？

Re:素因数分解はＰに入っていない（と思う）

[Anonymous Coward]

P≠NP の仮定の下で、P でもなく NP 完全でもないような NP 問題があることは示せます

これもそんなに簡単に示せます？

Re:素因数分解はＰに入っていない（と思う）

[tix (7637)]

これもそんなに簡単に示せます？

ぼくには簡単ではありませんが (^^;) Papadimitriou の Computational Complexity に証明が載っていました。対角線論法を使ってうまいこといったはず。

1ヶ月前に証明を読んだのに、もう忘れている……やばい……。

--
鵜呑みにしてみる？

Re:素因数分解はＰに入っていない（と思う）

[Anonymous Coward]

Papadimitriou の Computational Complexity に証明が載っていました。

あぁなるほど．ポインタありがとうございました．