パスワードを忘れた? アカウント作成
この議論は賞味期限が切れたので、アーカイブ化されています。 新たにコメントを付けることはできません。

次数27の最短ゴロム定規(OGR-27)が確定」記事へのコメント

  • そっちにはNP完全問題って間違ったことが書かれてコメントで突っ込まれてるけど(これが最短であることの検算も簡単ではないので明らかにNPに属さない)。

    • by Anonymous Coward on 2014年02月28日 14時53分 (#2553421)
      NP完全問題ではないのは、「検算も簡単ではない」というところから導き出される結論ではありません。
      まず、クラスNPと言った場合には、答えがtrueかfalseで得られるような判定問題だけをさしますので、そのギャップを埋める必要があります。

      例えば、よく引き合いに出される巡回セールスマン問題は「最短経路を求めよ」ですからクラスNPには属しません。
      でも、これを、「経路長X以下の経路が存在するか否か?」に書き換えるとこれはNP完全問題になります。
      この改造版の巡回セールスマン問題の場合の、「検算が多項式時間で出来る」は、
      「解候補が与えられた場合に、多項式時間で、それが正しい解、すなわち、『長さX未満の経路になっているかどうか』を判定できる」
      と言う意味になります。

      ゴロム定規問題の場合は、「長さX以下のY次ゴロム定規は存在するか?」と書き換えた問題を考えると、クラスNPには属します。
      ある定規の候補が与えられたときに、それが「長さX以下のY次ゴロム定規になっているか?」は簡単に判定できますので。
      ですので、検算が簡単かどうかと言う観点で見れば、最短ゴロム定規問題は、良くあるNP完全問題と似たような立ち位置にいます。

      ただ、次に、このように判定問題に書き換えた後の問題がNP完全かどうか、と言う壁があります。
      ある問題AがNP完全問題だと言うためには、おおざっぱに言うと、「A問題を高速に解くツール」があった時に、
      別のNP完全問題Bを、このツールを使って簡単に解くことができる必要があります。

      例えば、上記の改造版巡回セールスマン問題の場合、それを多項式時間で解くツールがあれば、それを使って別のNP完全問題、
      例えば、組み合わせ回路(論理回路)の出力がONになるような入力パターンは存在するか? と言う問題を多項式時間で解くことが出来たりします。

      最短ゴロム定規問題の場合は、この手の事をやる方法がまだ見つかっていないため、
      判定問題に書き換えてもNP完全とは言えないわけです。
      親コメント
      • ゴロム定規問題の場合は、「長さX以下のY次ゴロム定規は存在するか?」と書き換えた問題を考えると、クラスNPには属します。
        ある定規の候補が与えられたときに、それが「長さX以下のY次ゴロム定規になっているか?」は簡単に判定できますので。
        ですので、検算が簡単かどうかと言う観点で見れば、最短ゴロム定規問題は、良くあるNP完全問題と似たような立ち位置にいます。

        あなたはご存知で、話を省略しただけかもしれませんが、この議論には、入力 Y を tally 表現 (一進法) で与えるという前提が必要です。 Y が二進法で与えられている場合は、定規の候補を自明に記述するだけで入力の指数長の文字列になってしまうので。 (Y が二進法で与えられた場合にこの問題が NP に属するかどうかは知られていないと思います。)

        さらに、 Y を tally 表現で与えたとしても、この問題を「最短ゴロム定規問題の判定版」と考えるのが妥当かどうかは、巡回セールスマン問題の場合と違って検証を要します。

        巡回セールスマン問題の場合に、「各辺に自然数の重みが付いたグラフ G と自然数 X が与えられたときに、 G が経路長 X 以下のハミルトン閉路を持つかどうかを判定する問題」を「巡回セールスマン問題の判定版」と考えるのが妥当であるのは、元の問題と判定版とが同じ計算量である (正確には、互いに多項式時間チューリング還元できる) ことが簡単に示せるからです。一方、「自然数 Y が tally 表現で与えられたとき、最短の Y 次ゴロム定規を求める問題」を「最短ゴロム定規問題」と呼ぶことにして、この問題の計算量が「自然数 X が二進法で、自然数 Y が tally 表現で与えられたとき、長さ X 以下の Y 次ゴロム定規が存在するかどうかを判定する問題」の計算量以下である (最短ゴロム定規問題がこの判定問題に多項式時間チューリング還元できる) ことは簡単には示せないと思います。これが示せないと、例えば「この判定問題は P に属するけれど最短ゴロム定規問題は多項式時間では解けない」という可能性も否定できず、この判定問題を最短ゴロム定規問題の判定版と考えるのは妥当でないことになります。

        親コメント
        • by Anonymous Coward
          >あなたはご存知で、話を省略しただけかもしれませんが

          ご指摘ありがとうございます。そこまで深くは考えておらず見落としていました。
          候補の与え方の表現はいろいろありますが、使う/使わないを1/0に当てはめた2Yビットの整数として与えるのが定番ですね。

          >巡回セールスマン問題の場合に~判定版とが同じ計算量である

          ここは、もうすこし注意が必要なはずです。
          NP完全な「巡回セールスマン問題の判定問題版」の方を解いても、必ずしも、具体的な経路に関する情報が出てくるわけではありません
          • 候補の与え方の表現はいろいろありますが、使う/使わないを1/0に当てはめた2Yビットの整数として与えるのが定番ですね。

            それだと 2Y ビット必要なのでダメのような。

            定番というか、もっとも素朴な解の表現方法は、 Y 個の自然数を各々二進法で書くことだと思います。各自然数は X 以下なので、解の表現の長さが log X と Y の多項式で抑えられます。すなわち、 X が二進法、 Y が tally 表現で与えられているときに入力長の多項式で抑えられます。

            >巡回セールスマン問題の場合に~判定版とが同じ計算量である

            ここは、もうすこし注意が必要なはずです。

            注意が必要なのはその通りですが、僕が #2553635 で書いたことは正しいです。 :)

            この問題と互いに多項式時間チューリング還元出来るのは、「最短の経路長を求めよ」までで、
            「最短経路を求めよ」の方から還元可能かは自明ではなく、まだ方法が見つかってないはずです。

            いいえ、「最短経路長を求めよ」のバージョンも、「最短経路を求めよ」のバージョンも、判定版 (長さ X 以下の経路があるか?) に多項式時間チューリング還元できます。これら二つの性質は、巡回セールスマン問題の self-reducibility と呼ばれます。 (残念ながらこれら二つの性質は区別なく同じ名前で呼ばれることが多いので、多少混乱の元です。)

            証明は書かないので、考えてみてください。わからなければ TSP self-reducibility あたりで検索すれば証明かヒントかが見付かるかと思います。 (なお、検索してみると、学部の計算量理論の演習問題の定番のようです。)

            なので、

            ですので、まあ、巡回セールスマン問題は、よく言われるほどにはNP完全っぽい問題ではないということで、

            というのは正当な主張だと思いません。「長さ X 以下の経路があるか」という問題を巡回セールスマン問題の判定版と呼ぶのは上述のように正当化できる呼び方ですし、判定版が NP 完全であることをもって「巡回セールスマン問題は NP 完全である」と表現するのは (元の関数問題とその判定版を同じ言葉で呼ぶのは不正確であるという批判はありうるとしても) 言わんとするところは正しいと考えるべきだと思います。一方で、「長さ X 以下の Y 次ゴロム定規は存在するか?」という判定問題や #2553607 に出てくる「与えられた Y 次ゴロム定規は最短か?」という判定問題を最短ゴロム定規問題の判定版と考えるのは、最短ゴロム定規問題からこれらの判定問題への多項式チューリング還元が示されない限り、妥当でありません。

            親コメント

日本発のオープンソースソフトウェアは42件 -- ある官僚

処理中...