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

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

[saitoh (10803)]

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

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

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

[minyu (32684)]

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

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

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

[taka2 (14791)]

ちょっとわかりにくいですけど、元コメの主張は「いいわけ」から「反論の余地なし」に昇格するということでしょう。

「実用的な時間で厳密解を求めるのはたぶん無理だから、近似解を求めます」というと
「本当に無理なのか」と聞かれたら答えようのない「いいわけ」になってましたけど

「実用的な時間で厳密解を求めるのは不可能だと証明されているので、近似解を求めます」というと「反論の余地」がありません。

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

[Anonymous Coward]

>「本当に無理なのか」と聞かれたら

私が読んだ教科書には、

「私には解けません」→じゃあクビ、と言われかねない。
「私には解けませんが、世界中の数学者の誰もまだ解けていませんから私が殊更無能なわけではないです」→クビにしても解決しない。

というのが上手いいいわけの例として載ってました。

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

[saitoh (10803)]

わかりにくい書き方して済みません。

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

[SteppingWind (2654)]

言い訳が許されるのではなく「厳密解を求めるのは馬鹿」と言えるようになるんではないかと.

Re:

[Anonymous Coward]

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

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

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

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

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

[minyu (32684)]

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

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