巡回セールスマン問題: NPについて

　NP問題である巡回セールスマン問題について質問です．

　NP問題には，「非決定性チューリングマシンによって多項式時間で解くことができる決定問題」「証拠が与えられれば，その答えがYesであることを(問題の入力サイズに関する)多項式時間以内に確認することができる決定問題」などの定義があります．このふたつめの定義について質問です．

　巡回セールス問題における解を確かめる「証拠」とはいったいどのようなものなのでしょうか?

No.2 ベストアンサー 回答者： Tacosan 回答日時： 2005/01/14 19:01

「NP問題」は「決定問題」だと自ら書いているんですが....

「最短路を見つけろ」ではyes/noで答えられないので, 決定問題ではありません.

No.1 回答者： Tacosan 回答日時： 2005/01/13 22:40

巡回セールスマン問題そのものは最適化問題なんですが, これに対応する決定問題を作ることができてそれはNP問題となります(なので巡回セールスマン問題のような最適化問題を「NP最適化問題」と呼びます).

NP決定問題としての巡回セールスマン問題は「辺に重み(距離)の付いたグラフGと定数kが与えられたときに, 全ての頂点を1回ずつたどるような, 距離の合計がたかだかkである巡回路が存在するかどうか」という形になります. この形であれば「証拠」は簡単にわかると思いますが, 「全ての頂点を1回ずつたどるような, 距離の合計がたかだかkである巡回路」となります.

この回答への補足

　!! なんと! NP(決定)問題としては最短かどうかは不要なのですね・・・．

　どうやって最短性を証明するか(それ以下の距離では巡回できないことの証明)をずっと考えてました．

補足日時：2005/01/14 02:08