アカウント名:
パスワード:
ひらたくいうと(つまりかなりいいかげんで正しくない解説)、 「この問題は解候補をしらみつぶしに調べてゆくしかないので厳密解を得るのに時間が掛りすぎるので近似解を求めます」といって厳密解を求めない言い訳が許されてた問題群があります。実は厳密解を求めるのに時間が掛りすぎる(効率よく解くアルゴリズムが存在しない)とは証明されてなかった。 P!=NPだと確定すると、上記の「いいわけ」がいいわけではなくなる。 たとえば巡回セールスマン問題。
より多くのコメントがこの議論にあるかもしれませんが、JavaScriptが有効ではない環境を使用している場合、クラシックなコメントシステム(D1)に設定を変更する必要があります。
私は悩みをリストアップし始めたが、そのあまりの長さにいやけがさし、何も考えないことにした。-- Robert C. Pike
この予想それ自体の意味とか、証明の意義とか (スコア:2, 参考になる)
ひらたくいうと(つまりかなりいいかげんで正しくない解説)、 「この問題は解候補をしらみつぶしに調べてゆくしかないので厳密解を得るのに時間が掛りすぎるので近似解を求めます」といって厳密解を求めない言い訳が許されてた問題群があります。実は厳密解を求めるのに時間が掛りすぎる(効率よく解くアルゴリズムが存在しない)とは証明されてなかった。 P!=NPだと確定すると、上記の「いいわけ」がいいわけではなくなる。 たとえば巡回セールスマン問題。
Re: (スコア:1, 参考になる)
巡回セールスマン問題はNP困難だがNP完全ではない(すなわちNPよりもっと難しい)ため、P!=NPの話で持ち出すには不適当、つか全然関係ない。
Re:この予想それ自体の意味とか、証明の意義とか (スコア:1)