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

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

[Anonymous Coward]

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

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

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

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

[the Poster (3856)]

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

P≠NP　が成立するならば、その中間クラスが存在することがすぐに
言えますので、素因数分解はその難度からちょうどそのあたりにあるのでは、という感じです（少なくとも私の周りでの雰囲気です）。

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 に証明が載っていました。

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

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

[the Poster (3856)]

しまった、嘘かいてしまいました。
ご指摘の通りです。

言いたかったのは「P≠NP∩coNP」が成立するとして、
それの中間クラスに素因数分解が入るのでは、と予想している
という話でした。

これとPとNPの中間クラスの話は別物です。

ちょっと考えればすぐにわかるのに何でこんな勘違いしたのだろう…　
上の僕のコメント信じた人、ごめんなさい。