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

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

[saitoh (10803)]

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

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

Re:

[minyu (32684)]

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

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

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

[taka2 (14791)]

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

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

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

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

[Anonymous Coward]

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

私が読んだ教科書には、

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

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

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

[saitoh (10803)]

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