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

質問

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

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

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

回答No.2

Tacosan · ベストアンサー

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

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

回答No.1

Tacosan

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

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

補足

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

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