アカウント名:
パスワード:
ひらたくいうと(つまりかなりいいかげんで正しくない解説)、 「この問題は解候補をしらみつぶしに調べてゆくしかないので厳密解を得るのに時間が掛りすぎるので近似解を求めます」といって厳密解を求めない言い訳が許されてた問題群があります。実は厳密解を求めるのに時間が掛りすぎる(効率よく解くアルゴリズムが存在しない)とは証明されてなかった。 P!=NPだと確定すると、上記の「いいわけ」がいいわけではなくなる。 たとえば巡回セールスマン問題。
ちょっとわかりにくいですけど、元コメの主張は「いいわけ」から「反論の余地なし」に昇格するということでしょう。
「実用的な時間で厳密解を求めるのはたぶん無理だから、近似解を求めます」というと「本当に無理なのか」と聞かれたら答えようのない「いいわけ」になってましたけど
「実用的な時間で厳密解を求めるのは不可能だと証明されているので、近似解を求めます」というと「反論の余地」がありません。
>「本当に無理なのか」と聞かれたら
私が読んだ教科書には、
「私には解けません」→じゃあクビ、と言われかねない。「私には解けませんが、世界中の数学者の誰もまだ解けていませんから私が殊更無能なわけではないです」→クビにしても解決しない。
というのが上手いいいわけの例として載ってました。
言い訳が許されるのではなく「厳密解を求めるのは馬鹿」と言えるようになるんではないかと.
> P!=NPだと確定すると、上記の「いいわけ」がいいわけではなくなる。
ん? P!=NPだと「効率よく解くアルゴリズムが存在しない」のですから, 言い訳が許されていいのでは?# 揚げ足取りですみません...
「言い訳」では無く、「良い訳」になるのでは？
# 言い訳というと、ちょっと後ろ向きな誤魔化のイメージがありますが# そうせざるを得ないのだから、近似解が問題に対する「良いアプローチ」になるのだと思います。
その思い込みはそんなにまずくないと思った次第です。
TSPはNP困難かつNP-easy(日本語の定訳って無いんですかね? NP完全問題に対する効率的なアルゴリズムが存在すれば、同様に効率的に解ける問題のクラス)ですから、
TSPを解く効率的なアルゴリズムが存在する <--> P=NP
が成立しますし。どっちかの矢印が成立しないぐらいに外れた問題なら、全然関係ない、と思いますが。
NPのクラスに関する勉強をするとき以外はそんなに気にしなくても良いんじゃないかと。ちゃんとした教科書ならどう違うのかの説明から書いてありますから、その段になって誤解のしようはないですし。あと、論文とか、正式な文章を書くときには書き間違えないよう注意すること。逆に会話だと、間違って指摘しての応酬が時間の無駄なので、「この問題はNPなので」とかぼかすのがコツ。
より多くのコメントがこの議論にあるかもしれませんが、JavaScriptが有効ではない環境を使用している場合、クラシックなコメントシステム(D1)に設定を変更する必要があります。
犯人は巨人ファンでA型で眼鏡をかけている -- あるハッカー
この予想それ自体の意味とか、証明の意義とか (スコア:2, 参考になる)
ひらたくいうと(つまりかなりいいかげんで正しくない解説)、 「この問題は解候補をしらみつぶしに調べてゆくしかないので厳密解を得るのに時間が掛りすぎるので近似解を求めます」といって厳密解を求めない言い訳が許されてた問題群があります。実は厳密解を求めるのに時間が掛りすぎる(効率よく解くアルゴリズムが存在しない)とは証明されてなかった。 P!=NPだと確定すると、上記の「いいわけ」がいいわけではなくなる。 たとえば巡回セールスマン問題。
Re:この予想それ自体の意味とか、証明の意義とか (スコア:1)
ん? P!=NPだと「効率よく解くアルゴリズムが存在しない」のですから, 言い訳が許されていいのでは?
# 揚げ足取りですみません...
Re:この予想それ自体の意味とか、証明の意義とか (スコア:4, 参考になる)
ちょっとわかりにくいですけど、元コメの主張は「いいわけ」から「反論の余地なし」に昇格するということでしょう。
「実用的な時間で厳密解を求めるのはたぶん無理だから、近似解を求めます」というと
「本当に無理なのか」と聞かれたら答えようのない「いいわけ」になってましたけど
「実用的な時間で厳密解を求めるのは不可能だと証明されているので、近似解を求めます」というと「反論の余地」がありません。
Re:この予想それ自体の意味とか、証明の意義とか (スコア:1, 興味深い)
>「本当に無理なのか」と聞かれたら
私が読んだ教科書には、
「私には解けません」→じゃあクビ、と言われかねない。
「私には解けませんが、世界中の数学者の誰もまだ解けていませんから私が殊更無能なわけではないです」→クビにしても解決しない。
というのが上手いいいわけの例として載ってました。
Re:この予想それ自体の意味とか、証明の意義とか (スコア:1)
Re:この予想それ自体の意味とか、証明の意義とか (スコア:1)
言い訳が許されるのではなく「厳密解を求めるのは馬鹿」と言えるようになるんではないかと.
Re: (スコア:0)
> P!=NPだと確定すると、上記の「いいわけ」がいいわけではなくなる。
ん? P!=NPだと「効率よく解くアルゴリズムが存在しない」のですから, 言い訳が許されていいのでは?
# 揚げ足取りですみません...
「言い訳」では無く、「良い訳」になるのでは？
# 言い訳というと、ちょっと後ろ向きな誤魔化のイメージがありますが
# そうせざるを得ないのだから、近似解が問題に対する「良いアプローチ」になるのだと思います。
Re:この予想それ自体の意味とか、証明の意義とか (スコア:1)
> 「言い訳」では無く、「良い訳」になるのでは？
最初, 言い訳が「良いわけでなくなる」, と読みました。つまり効率よく求められるんだろう? と。
でも, 言い訳が「言い訳でなくなる」, つまり, 正当な理由となる, と読むべきだったんですね。
PvsNP問題で興奮しすぎて, 脊髄反射してしまったようです。
元コメは正しく読めましたね。
すみません。
Re:この予想それ自体の意味とか、証明の意義とか (スコア:1, 参考になる)
巡回セールスマン問題はNP困難だがNP完全ではない(すなわちNPよりもっと難しい)ため、P!=NPの話で持ち出すには不適当、つか全然関係ない。
Re:この予想それ自体の意味とか、証明の意義とか (スコア:1)
Re: (スコア:0)
Re: (スコア:0)
特にsaitoh氏は教育者だということなので、コメを読んで「TSPはNP(完全)」だと思い込む人が出るのはまずい。俺もつられそうになったもん、絶対いるはずだよ。
Re: (スコア:0)
その思い込みはそんなにまずくないと思った次第です。
TSPはNP困難かつNP-easy(日本語の定訳って無いんですかね? NP完全問題に対する効率的なアルゴリズムが存在すれば、同様に効率的に解ける問題のクラス)ですから、
TSPを解く効率的なアルゴリズムが存在する <--> P=NP
が成立しますし。どっちかの矢印が成立しないぐらいに外れた問題なら、全然関係ない、と思いますが。
NPのクラスに関する勉強をするとき以外はそんなに気にしなくても良いんじゃないかと。
ちゃんとした教科書ならどう違うのかの説明から書いてありますから、その段になって誤解のしようはないですし。
あと、論文とか、正式な文章を書くときには書き間違えないよう注意すること。
逆に会話だと、間違って指摘しての応酬が時間の無駄なので、「この問題はNPなので」とかぼかすのがコツ。
Re: (スコア:0)
＿＿＿＿_＿
／＿ |
/. ＼￣￣￣￣|
/ ／ ― ― |
| / - - |
||| (6 > |
| | | ┏━┓| ／￣￣￣￣￣￣￣￣
| | | | ┃─┃| ＜ 正直、すまんかった。
|| | | | ＼ ┃ ┃/ ＼＿＿＿＿＿＿＿＿
| || | | ￣ ￣|
Re: (スコア:0)
その「ちょこっと」が問題の本質にかかわってくるのでダメでしょう。
Re: (スコア:0)