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

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

[saitoh (10803)]

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

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

Re:

[Anonymous Coward]

> たとえば巡回セールスマン問題。

巡回セールスマン問題はNP困難だがNP完全ではない(すなわちNPよりもっと難しい)ため、P!=NPの話で持ち出すには不適当、つか全然関係ない。

Re:

[Anonymous Coward]

巡回セールスマン問題は「最短距離となる経路を求めよ」だからNP困難だけど、「距離X未満の経路が存在するか?」に問題をちょこっと書き換えるとNP完全。厳密に数学的な議論をするんでなければ、十分に適当な例だし、十分に関係してる。

Re:

[Anonymous Coward]

それなら最初から有名なハミルトン閉路問題を出した方がよいでしょう。
特にsaitoh氏は教育者だということなので、コメを読んで「TSPはNP(完全)」だと思い込む人が出るのはまずい。俺もつられそうになったもん、絶対いるはずだよ。

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

[Anonymous Coward]

その思い込みはそんなにまずくないと思った次第です。

TSPはNP困難かつNP-easy(日本語の定訳って無いんですかね? NP完全問題に対する効率的なアルゴリズムが存在すれば、同様に効率的に解ける問題のクラス)ですから、

TSPを解く効率的なアルゴリズムが存在する <--> P=NP

が成立しますし。どっちかの矢印が成立しないぐらいに外れた問題なら、全然関係ない、と思いますが。

NPのクラスに関する勉強をするとき以外はそんなに気にしなくても良いんじゃないかと。
ちゃんとした教科書ならどう違うのかの説明から書いてありますから、その段になって誤解のしようはないですし。
あと、論文とか、正式な文章を書くときには書き間違えないよう注意すること。
逆に会話だと、間違って指摘しての応酬が時間の無駄なので、「この問題はNPなので」とかぼかすのがコツ。

Re:

[Anonymous Coward]

俺の勘違いだった。恥ずかしいのでAAでごまかす。
　　　　　　　　＿＿＿＿_＿
　　　　　　 ／＿　　　　　　|
　　　　 　 /.　＼￣￣￣￣|
　　　　　/　　／　 ―　― |
　　　　　|　 /　　 　-　　- |
　　　　 ||| (6　　　　　　>　|
　　　　| | |　　　　 ┏━┓|　 　 ／￣￣￣￣￣￣￣￣
　　　| | | | 　　　　┃─┃|　 ＜　正直、すまんかった。
　　　|| | | | 　＼　┃　 ┃/　 　 ＼＿＿＿＿＿＿＿＿
　　　| || |　|　　　￣　￣|