あなたはご存知で、話を省略しただけかもしれませんが、この議論には、入力 Y を tally 表現 (一進法) で与えるという前提が必要です。 Y が二進法で与えられている場合は、定規の候補を自明に記述するだけで入力の指数長の文字列になってしまうので。 (Y が二進法で与えられた場合にこの問題が NP に属するかどうかは知られていないと思います。)
さらに、 Y を tally 表現で与えたとしても、この問題を「最短ゴロム定規問題の判定版」と考えるのが妥当かどうかは、巡回セールスマン問題の場合と違って検証を要します。
巡回セールスマン問題の場合に、「各辺に自然数の重みが付いたグラフ G と自然数 X が与えられたときに、 G が経路長 X 以下のハミルトン閉路を持つかどうかを判定する問題」を「巡回セールスマン問題の判定版」と考えるのが妥当であるのは、元の問題と判定版とが同じ計算量である (正確には、互いに多項式時間チューリング還元できる) ことが簡単に示せるからです。一方、「自然数 Y が tally 表現で与えられたとき、最短の Y 次ゴロム定規を求める問題」を「最短ゴロム定規問題」と呼ぶことにして、この問題の計算量が「自然数 X が二進法で、自然数 Y が tally 表現で与えられたとき、長さ X 以下の Y 次ゴロム定規が存在するかどうかを判定する問題」の計算量以下である (最短ゴロム定規問題がこの判定問題に多項式時間チューリング還元できる) ことは簡単には示せないと思います。これが示せないと、例えば「この判定問題は P に属するけれど最短ゴロム定規問題は多項式時間では解けない」という可能性も否定できず、この判定問題を最短ゴロム定規問題の判定版と考えるのは妥当でないことになります。
というのは正当な主張だと思いません。「長さ X 以下の経路があるか」という問題を巡回セールスマン問題の判定版と呼ぶのは上述のように正当化できる呼び方ですし、判定版が NP 完全であることをもって「巡回セールスマン問題は NP 完全である」と表現するのは (元の関数問題とその判定版を同じ言葉で呼ぶのは不正確であるという批判はありうるとしても) 言わんとするところは正しいと考えるべきだと思います。一方で、「長さ X 以下の Y 次ゴロム定規は存在するか?」という判定問題や #2553607 に出てくる「与えられた Y 次ゴロム定規は最短か?」という判定問題を最短ゴロム定規問題の判定版と考えるのは、最短ゴロム定規問題からこれらの判定問題への多項式チューリング還元が示されない限り、妥当でありません。
OGR-25確定時の関連ストーリーも参照 (スコア:1)
そっちにはNP完全問題って間違ったことが書かれてコメントで突っ込まれてるけど(これが最短であることの検算も簡単ではないので明らかにNPに属さない)。
Re:OGR-25確定時の関連ストーリーも参照 (スコア:2)
「検算が簡単ではない」と言っても、今のところ検算を効率良く行う方法が知られていないというだけなので、それを理由に「明らかに NP に属さない」と言うことはできないよ。
なお、次数 25 のときのコメントで deraok さん [srad.jp]が
と書いているのは、 NP というのが「はい」か「いいえ」で答えられる問題 (「判定問題」と呼ばれる) のクラスだからだと思う。検算が簡単かどうか以前の問題として、最短ゴロム定規を「求める」問題は判定問題でないので、明らかに NP に属さない、ということ。
実際には、習慣上、問題によっては判定問題でなくても「NP に属する」とか「NP 完全である」という言葉を使う場合があるけれど、習慣として確立している場合以外に使うと意味が通じない。最短ゴロム定規を求める問題についてはそういう習慣が確立していないので、どういう判定問題を考えるのかを定義することなしにいきなり「NP に属する」と言ったら、意味が通じない。
Re: (スコア:0)
なんか問題をクラスNPに属するようにするためだけに不自然な書き換えしてるように見えるんだけど。
巡回セールスマン問題なら「与えられた経路は最短かどうか」最短ゴロム定規問題なら「与えられたY次ゴロム定規は最短かどうか」というのは自明すぎてわざわざ言うまでもないと思ってたのに2つも独立して突っ込まれてるし。
Re:OGR-25確定時の関連ストーリーも参照 (スコア:2)
どの問題のことを言っているのか不明。僕は #2553317 で NP に属する判定問題を 1 個も書いていない。
それは巡回セールスマン問題ではない。あえて呼ぶなら「巡回セールスマン検算問題」とでも呼ぶべき問題。同様に、
それは最短ゴロム定規問題ではなく「最短ゴロム定規検算問題」とでも呼ぶべき問題。
しかも、あなたの書いた問題はどちらも、 NP に属さないことは証明されていない。詳細は省くけど、これらの問題は coNP というクラスに属するので、仮にいずれかが NP に属さないことが証明されれば P≠NP が証明される。なので、仮に #2553224 が最短ゴロム定規検算問題のことを言っていたとしても、「これが最短であることの検算も簡単ではないので明らかに NP に属さない」と書いてあるのは依然として誤り。
Re: (スコア:0)
>なんか問題をクラスNPに属するようにするためだけに不自然な書き換えしてるように見えるんだけど。
不自然でもなんでも、クラスNPに属するように書き換えない限りは、
「クラスNPに関する知識」という強力な道具を使って議論が出来ないので、しょうがないんです。
クラスNPに突っ込めないような、より特殊で複雑な問題をそのまま議論するのであれば、
クラスNPに関してよく知られた知識を使わずに頑張る必要があります。
どこから手を付ければ良いやらという話になりますので、ここでの雑談の域を超えるでしょ
Re: (スコア:0)
まず、クラスNPと言った場合には、答えがtrueかfalseで得られるような判定問題だけをさしますので、そのギャップを埋める必要があります。
例えば、よく引き合いに出される巡回セールスマン問題は「最短経路を求めよ」ですからクラスNPには属しません。
でも、これを、「経路長X以下の経路が存在するか否か?」に書き換えるとこれはNP完全問題になります。
この改造版の巡回セールスマン問題の場合の、「検算が多項式時間で出来る」は、
「解候補が与えられた場合に、多
Re:OGR-25確定時の関連ストーリーも参照 (スコア:2)
あなたはご存知で、話を省略しただけかもしれませんが、この議論には、入力 Y を tally 表現 (一進法) で与えるという前提が必要です。 Y が二進法で与えられている場合は、定規の候補を自明に記述するだけで入力の指数長の文字列になってしまうので。 (Y が二進法で与えられた場合にこの問題が NP に属するかどうかは知られていないと思います。)
さらに、 Y を tally 表現で与えたとしても、この問題を「最短ゴロム定規問題の判定版」と考えるのが妥当かどうかは、巡回セールスマン問題の場合と違って検証を要します。
巡回セールスマン問題の場合に、「各辺に自然数の重みが付いたグラフ G と自然数 X が与えられたときに、 G が経路長 X 以下のハミルトン閉路を持つかどうかを判定する問題」を「巡回セールスマン問題の判定版」と考えるのが妥当であるのは、元の問題と判定版とが同じ計算量である (正確には、互いに多項式時間チューリング還元できる) ことが簡単に示せるからです。一方、「自然数 Y が tally 表現で与えられたとき、最短の Y 次ゴロム定規を求める問題」を「最短ゴロム定規問題」と呼ぶことにして、この問題の計算量が「自然数 X が二進法で、自然数 Y が tally 表現で与えられたとき、長さ X 以下の Y 次ゴロム定規が存在するかどうかを判定する問題」の計算量以下である (最短ゴロム定規問題がこの判定問題に多項式時間チューリング還元できる) ことは簡単には示せないと思います。これが示せないと、例えば「この判定問題は P に属するけれど最短ゴロム定規問題は多項式時間では解けない」という可能性も否定できず、この判定問題を最短ゴロム定規問題の判定版と考えるのは妥当でないことになります。
Re: (スコア:0)
ご指摘ありがとうございます。そこまで深くは考えておらず見落としていました。
候補の与え方の表現はいろいろありますが、使う/使わないを1/0に当てはめた2Yビットの整数として与えるのが定番ですね。
>巡回セールスマン問題の場合に～判定版とが同じ計算量である
ここは、もうすこし注意が必要なはずです。
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 次ゴロム定規は最短か?」という判定問題を最短ゴロム定規問題の判定版と考えるのは、最短ゴロム定規問題からこれらの判定問題への多項式チューリング還元が示されない限り、妥当でありません。