というのは正当な主張だと思いません。「長さ X 以下の経路があるか」という問題を巡回セールスマン問題の判定版と呼ぶのは上述のように正当化できる呼び方ですし、判定版が NP 完全であることをもって「巡回セールスマン問題は NP 完全である」と表現するのは (元の関数問題とその判定版を同じ言葉で呼ぶのは不正確であるという批判はありうるとしても) 言わんとするところは正しいと考えるべきだと思います。一方で、「長さ X 以下の Y 次ゴロム定規は存在するか?」という判定問題や #2553607 に出てくる「与えられた Y 次ゴロム定規は最短か?」という判定問題を最短ゴロム定規問題の判定版と考えるのは、最短ゴロム定規問題からこれらの判定問題への多項式チューリング還元が示されない限り、妥当でありません。
OGR-25確定時の関連ストーリーも参照 (スコア:1)
そっちにはNP完全問題って間違ったことが書かれてコメントで突っ込まれてるけど(これが最短であることの検算も簡単ではないので明らかにNPに属さない)。
Re: (スコア:0)
まず、クラスNPと言った場合には、答えがtrueかfalseで得られるような判定問題だけをさしますので、そのギャップを埋める必要があります。
例えば、よく引き合いに出される巡回セールスマン問題は「最短経路を求めよ」ですからクラスNPには属しません。
でも、これを、「経路長X以下の経路が存在するか否か?」に書き換えるとこれはNP完全問題になります。
この改造版の巡回セールスマン問題の場合の、「検算が多項式時間で出来る」は、
「解候補が与えられた場合に、多
Re: (スコア:2)
あなたはご存知で、話を省略しただけかもしれませんが、この議論には、入力 Y を tally 表現 (一進法) で与えるという前提が必要です。 Y が二進法で与えられている場合は、定規の候補を自明に記
Re:OGR-25確定時の関連ストーリーも参照 (スコア:0)
ご指摘ありがとうございます。そこまで深くは考えておらず見落としていました。
候補の与え方の表現はいろいろありますが、使う/使わないを1/0に当てはめた2Yビットの整数として与えるのが定番ですね。
>巡回セールスマン問題の場合に～判定版とが同じ計算量である
ここは、もうすこし注意が必要なはずです。
NP完全な「巡回セールスマン問題の判定問題版」の方を解いても、必ずしも、具体的な経路に関する情報が出てくるわけではありませんので。
この問題と互いに多項式時間チューリング還元出来るのは、「最短の経路長を求めよ」までで、
「最短経路を求めよ」の方から還元可能かは自明ではなく、まだ方法が見つかってないはずです。
後の論はおっしゃるとおりだと思います。
ですので、まあ、巡回セールスマン問題は、よく言われるほどにはNP完全っぽい問題ではないということで、
それを引き合いに出してきたのは混乱の元ではあるんですが。
Re:OGR-25確定時の関連ストーリーも参照 (スコア:2)
それだと 2Y ビット必要なのでダメのような。
定番というか、もっとも素朴な解の表現方法は、 Y 個の自然数を各々二進法で書くことだと思います。各自然数は X 以下なので、解の表現の長さが log X と Y の多項式で抑えられます。すなわち、 X が二進法、 Y が tally 表現で与えられているときに入力長の多項式で抑えられます。
注意が必要なのはその通りですが、僕が #2553635 で書いたことは正しいです。 :)
いいえ、「最短経路長を求めよ」のバージョンも、「最短経路を求めよ」のバージョンも、判定版 (長さ X 以下の経路があるか?) に多項式時間チューリング還元できます。これら二つの性質は、巡回セールスマン問題の self-reducibility と呼ばれます。 (残念ながらこれら二つの性質は区別なく同じ名前で呼ばれることが多いので、多少混乱の元です。)
証明は書かないので、考えてみてください。わからなければ TSP self-reducibility あたりで検索すれば証明かヒントかが見付かるかと思います。 (なお、検索してみると、学部の計算量理論の演習問題の定番のようです。)
なので、
というのは正当な主張だと思いません。「長さ X 以下の経路があるか」という問題を巡回セールスマン問題の判定版と呼ぶのは上述のように正当化できる呼び方ですし、判定版が NP 完全であることをもって「巡回セールスマン問題は NP 完全である」と表現するのは (元の関数問題とその判定版を同じ言葉で呼ぶのは不正確であるという批判はありうるとしても) 言わんとするところは正しいと考えるべきだと思います。一方で、「長さ X 以下の Y 次ゴロム定規は存在するか?」という判定問題や #2553607 に出てくる「与えられた Y 次ゴロム定規は最短か?」という判定問題を最短ゴロム定規問題の判定版と考えるのは、最短ゴロム定規問題からこれらの判定問題への多項式チューリング還元が示されない限り、妥当でありません。