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

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

[saitoh (10803)]

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

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

Re:

[minyu (32684)]

> P!=NPだと確定すると、上記の「いいわけ」がいいわけではなくなる。

ん? P!=NPだと「効率よく解くアルゴリズムが存在しない」のですから, 言い訳が許されていいのでは?
# 揚げ足取りですみません...

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

[Anonymous Coward]

> P!=NPだと確定すると、上記の「いいわけ」がいいわけではなくなる。

ん? P!=NPだと「効率よく解くアルゴリズムが存在しない」のですから, 言い訳が許されていいのでは?
# 揚げ足取りですみません...

「言い訳」では無く、「良い訳」になるのでは？

# 言い訳というと、ちょっと後ろ向きな誤魔化のイメージがありますが
# そうせざるを得ないのだから、近似解が問題に対する「良いアプローチ」になるのだと思います。

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

[minyu (32684)]

> 上記の「いいわけ」がいいわけではなくなる。
> 「言い訳」では無く、「良い訳」になるのでは？

最初, 言い訳が「良いわけでなくなる」, と読みました。つまり効率よく求められるんだろう? と。
でも, 言い訳が「言い訳でなくなる」, つまり, 正当な理由となる, と読むべきだったんですね。
PvsNP問題で興奮しすぎて, 脊髄反射してしまったようです。
元コメは正しく読めましたね。
すみません。