アカウント名:
パスワード:
P≠NP が成立するならば、その中間クラスが存在することがすぐに言えますので
より多くのコメントがこの議論にあるかもしれませんが、JavaScriptが有効ではない環境を使用している場合、クラシックなコメントシステム(D1)に設定を変更する必要があります。
Stay hungry, Stay foolish. -- Steven Paul Jobs
素因数分解もPに入っている (スコア:0)
量子コンピュータでできちゃうし、本物のNPハードよりは少し簡単だという感じがあるのだろうか。
専門家の方、そのあたりの雰囲気はどうなんですか?
素因数分解はPに入っていない(と思う) (スコア:4, 参考になる)
素因数分解はPではないと思われています。
でも、NP-complete(決定問題の場合ね)でもないと思われています。
じゃあ結局どこに入るのだといいますと、その中間のクラス。
P
Re:素因数分解はPに入っていない(と思う) (スコア:0)
Re:素因数分解はPに入っていない(と思う) (スコア:1)
ご指摘の通りです。
言いたかったのは「P≠NP∩coNP」が成立するとして、
それの中間クラスに素因数分解が入るのでは、と予想している
という話でした。
これとPとNPの中間クラスの話は別物です。
ちょっと考えればすぐにわかるのに何でこんな勘違いしたのだろう…
上の僕のコメント信じた人、ごめんなさい。