「P!=NP 予想、証明されるか ?」記事へのコメント

この予想それ自体の意味とか、証明の意義とか

[saitoh (10803)]

解説お願いしますって・・・。 たれ込み人が自分でリンクを張ったwikipediaにちゃんとまるまる解説されてますので、わざわざ書くのも何ですが。。。。

ひらたくいうと(つまりかなりいいかげんで正しくない解説)、 「この問題は解候補をしらみつぶしに調べてゆくしかないので厳密解を得るのに時間が掛りすぎるので近似解を求めます」といって厳密解を求めない言い訳が許されてた問題群があります。実は厳密解を求めるのに時間が掛りすぎる(効率よく解くアルゴリズムが存在しない)とは証明されてなかった。 P!=NPだと確定すると、上記の「いいわけ」がいいわけではなくなる。 たとえば巡回セールスマン問題。

Re:この予想それ自体の意味とか、証明の意義とか

[Anonymous Coward]

どうでもいいがNP完全とNP困難をごっちゃにしていないか