「3SAT問題を多項式時間で解くアルゴリズムが発表される。P=NP証明に？」記事へのコメント

TSP は NP 完全問題？

[Anonymous Coward]

リンク先の資料に 「巡回セールスマン問題はNP完全問題」 ってあるけど、NP困難じゃなかったっけ？

Re:

[Anonymous Coward]

リンク先に「予算内の経路」ってあるから判定問題にしている。だから完全だね。

Re:

[s02222 (20350)]

TSPの場合、「予算内に収まる経路があるかないか?」がNP完全問題バージョンで、「最も安い経路を探せ」がNP困難問題バージョン。

NP完全問題が「あらゆるクラスNPの問題より難しく(すなわち、その問題を速く解くアルゴリズムを応用すれば全てのクラスNPの問題がさくさく解ける)」「YesかNoか?を求める問題」と定義できるから。

基本的に完全問題バージョンと困難問題バージョンがある問題の場合は、どっちかを速く解けるアルゴリズムが見つかれば逆もまたしかりなので、厳密な議論をしている場合を除くと意識してない事が多く、慌ててしゃべってるときなん

Re:TSP は NP 完全問題？

[Anonymous Coward]

NP-hard と呼ばれるのは、TSPで予算内に収まるかどうかだけでも既に NPC なので、最安値はいくらかとか、最安経路を求めるなど様々な実用的なバリエーションに予算内判定を帰着できるからでしょう。

で、二分探索を簡単に考えていますが、「解ける」をどう捉えるかが問題です。 非決定性の計算は受理計算が存在するかだけなので、単なる非決定性のチューリング機械では多項式時間で最安値を求めることも、与えられた値が最安値かどうかを判定することもできないと思います。 予算内判定を多項式時間で yes, no を判別できれば最安値判定問題が解けます(Δ^p ₂-completeだったはず)。 あと、最安経路は複数存在しますので、予算内判定問題が簡単でも最安経路を求めるのはそれほど自明ではありません(関数のクラスとしてはΔ^p ₂MVかな？)。

Re:TSP は NP 完全問題？

[s02222 (20350)]

なるほど。たとえ「最安値は○○円です」までたどり着けても「どの経路が最安値になるか」が求まってるとは限らないわけですね。思い違いしていました。