パスワードを忘れた? アカウント作成
10711983 story
数学

次数27の最短ゴロム定規(OGR-27)が確定 24

ストーリー by hylom
いまそこにある問題 部門より
nyagy 曰く、

分散コンピューティングプロジェクト「distributed.net」が、OGR(最短ゴロム定規)の次数27(OGR-27)が確定したことを発表した(distributed.netのスタッフブログ)。

確定したOGR-27は、

0 3 15 41 66 95 97 106 142 152 220 221 225 242 295 330 338 354 382 388 402 415 486 504 523 546 553

であった。OGR-27の探索には19,919人が参加し、1,822日を費やしている(OGR-27 / Overall Project Stats)。

ゴロム定規とは構成する数値間の差が全て異なるものをいう。次数3の場合、0 1 3はゴロム定規となる。ゴロム定規は無限に存在するが、そのうち最も短いものを最短ゴロム定規という。最短ゴロム定規を効率的に求める方法は現在のところ知られておらず、候補となるゴロム定規を全て列挙してその内の最短となるものを探すしかない。

なお、distributed.netでは既にOGR-28の探索を開始している。

この議論は賞味期限が切れたので、アーカイブ化されています。 新たにコメントを付けることはできません。
  • by ReijiKurosaki (46559) on 2014年02月28日 10時09分 (#2553295)
    --
    /.jで検索してもスラドが出ないからbingはダメなんだよ
  • by Anonymous Coward on 2014年02月28日 6時44分 (#2553224)

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

    • (これが最短であることの検算も簡単ではないので明らかにNPに属さない)

      「検算が簡単ではない」と言っても、今のところ検算を効率良く行う方法が知られていないというだけなので、それを理由に「明らかに NP に属さない」と言うことはできないよ。

      なお、次数 25 のときのコメントで deraok さん [srad.jp]が

      というか、最短ゴロム定規を「求める」のは明らかにNPに属さない(⇒NP完全ではない)ですね。

      と書いているのは、 NP というのが「はい」か「いいえ」で答えられる問題 (「判定問題」と呼ばれる) のクラスだからだと思う。検算が簡単かどうか以前の問題として、最短ゴロム定規を「求める」問題は判定問題でないので、明らかに NP に属さない、ということ。

      実際には、習慣上、問題によっては判定問題でなくても「NP に属する」とか「NP 完全である」という言葉を使う場合があるけれど、習慣として確立している場合以外に使うと意味が通じない。最短ゴロム定規を求める問題についてはそういう習慣が確立していないので、どういう判定問題を考えるのかを定義することなしにいきなり「NP に属する」と言ったら、意味が通じない。

      親コメント
      • by Anonymous Coward

        なんか問題をクラスNPに属するようにするためだけに不自然な書き換えしてるように見えるんだけど。
        巡回セールスマン問題なら「与えられた経路は最短かどうか」最短ゴロム定規問題なら「与えられたY次ゴロム定規は最短かどうか」というのは自明すぎてわざわざ言うまでもないと思ってたのに2つも独立して突っ込まれてるし。

        • なんか問題をクラスNPに属するようにするためだけに不自然な書き換えしてるように見えるんだけど。

          どの問題のことを言っているのか不明。僕は #2553317 で NP に属する判定問題を 1 個も書いていない。

          巡回セールスマン問題なら「与えられた経路は最短かどうか」

          それは巡回セールスマン問題ではない。あえて呼ぶなら「巡回セールスマン検算問題」とでも呼ぶべき問題。同様に、

          最短ゴロム定規問題なら「与えられたY次ゴロム定規は最短かどうか」

          それは最短ゴロム定規問題ではなく「最短ゴロム定規検算問題」とでも呼ぶべき問題。

          しかも、あなたの書いた問題はどちらも、 NP に属さないことは証明されていない。詳細は省くけど、これらの問題は coNP というクラスに属するので、仮にいずれかが NP に属さないことが証明されれば P≠NP が証明される。なので、仮に #2553224 が最短ゴロム定規検算問題のことを言っていたとしても、「これが最短であることの検算も簡単ではないので明らかに NP に属さない」と書いてあるのは依然として誤り。

          親コメント
        • by Anonymous Coward
          コメント先を間違えておられる気がしましたので、コメント返します。

          >なんか問題をクラスNPに属するようにするためだけに不自然な書き換えしてるように見えるんだけど。

          不自然でもなんでも、クラスNPに属するように書き換えない限りは、
          「クラスNPに関する知識」という強力な道具を使って議論が出来ないので、しょうがないんです。

          クラスNPに突っ込めないような、より特殊で複雑な問題をそのまま議論するのであれば、
          クラスNPに関してよく知られた知識を使わずに頑張る必要があります。
          どこから手を付ければ良いやらという話になりますので、ここでの雑談の域を超えるでしょ
    • by Anonymous Coward
      NP完全問題ではないのは、「検算も簡単ではない」というところから導き出される結論ではありません。
      まず、クラスNPと言った場合には、答えがtrueかfalseで得られるような判定問題だけをさしますので、そのギャップを埋める必要があります。

      例えば、よく引き合いに出される巡回セールスマン問題は「最短経路を求めよ」ですからクラスNPには属しません。
      でも、これを、「経路長X以下の経路が存在するか否か?」に書き換えるとこれは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 次ゴロム定規は最短か?」という判定問題を最短ゴロム定規問題の判定版と考えるのは、最短ゴロム定規問題からこれらの判定問題への多項式チューリング還元が示されない限り、妥当でありません。

            親コメント
  • by Anonymous Coward on 2014年02月28日 9時19分 (#2553260)

    そんなことができるのか?

    • by Anonymous Coward
      「候補となるゴロム定規を全て列挙」は有限の時間で出来るでしょ。
      最短でないものが一つあればいいんだから。
    • by Anonymous Coward

      選択公理だ。

    • by Anonymous Coward

      今回の例でいえば、

      1~1000までの数字から27個選んで条件(構成する数値間の差が全て異なる)に当てはまるものを探す。
       ⇒
        分岐1: あれば、見つかったうちの最短のものが求める答え 
        分岐2: なければ、捜索範囲を1~10000に変えて自分を再帰呼び出し。

      これでできるでしょ?
      コード化するのも簡単そうだし、分散化するのも容易そう。私はやりたくないけど

    • by Anonymous Coward
      遅延評価とか、lazyとかのキーワードでググれ。まさに、

      無限の数を列挙します。それを順に条件を満たすものが出てくるまで調べます。最初に見つけた解がすなわち最小の解です。

      というような書き方をすることで、ある種のアルゴリズムを簡潔に記述するテクが有る。

      実際には、ライブラリやらインタプリタやらが上手いことやってくれるので、無限の数列なんかは作られず、
      順に調べるところで、必要に応じて順に増やしていくような動作になる。
  • by Anonymous Coward on 2014年02月28日 10時21分 (#2553304)

    探索したくなる人が沢山いるのだから面白いと思う人は結構いるということなんだけど…
    これがNP完全なのか証明するとかなら面白いと思うけど
    総当たりで探すテーマとしてとっつきやすいから使われてるだけ?

    • ウィキペディア [wikipedia.org]によれば

      最短ゴロム定規は、フェーズドアレイレーダー [wikipedia.org]の設計、電波望遠鏡 [wikipedia.org]の配置などに応用されている。

      だそうだから、計算結果には使い道があるらしいよ。これらの応用で「最短」であることにどれほどの意味があるかは知らないけど。

      あとは、 1 台の計算機では手に負えなさそうな計算を、地理的にも性能的にもばらばらな計算機の寄り集まりである分散環境で実現できるってのは、計算内容が何であれ、ある意味面白いんじゃない?

      親コメント
      • by Anonymous Coward

        最も耳障りで美しくない音楽をつくって [gizmodo.jp]人をイラッとさせることができます。
        # 最短であることに意味はないけど。

        • by Anonymous Coward

          数学者が音楽に手を出すより、音楽家が「いラ」っとさせる精度に関しては高いことがわかった。
          さすが専門家というべきか。

      • by Anonymous Coward

        ウィキペディア [wikipedia.org]によれば

        最短ゴロム定規は、フェーズドアレイレーダー [wikipedia.org]の設計、電波望遠鏡 [wikipedia.org]の配置などに応用されている。

        だそうだから、計算結果には使い道があるらしいよ。これらの応用で「最短」であることにどれほどの意味があるかは知らないけど。

        さすが

        • 情報ありがとうございます。それだと、計算結果自体には今のところ特に意味はない、という感じになるのでしょうか (ご存じでしたら)。万一、計算結果から一般の次数 n の最短ゴロム定規について何か規則性が見えてきたら、話はがらっと変わるのでしょうけれど。

          親コメント
          • by Anonymous Coward

            意味が無いというわけではなくて、すぐに実用に結びつくような結果が出てくるわけでは無いということです(もう実用アレコレのずっと先に到達してしまってる.....)

            • お返事ありがとうございます。 #2553640 で

              計算結果自体には今のところ特に意味はない、という感じになるのでしょうか

              と書いたのは不適切でした。「計算結果自体には今のところ特に応用先はない」と言いたかったのでした。

              親コメント
            • by Anonymous Coward

              Bitcoinでも掘ったほうがすぐ金になるだけよっぽどマシだな。

typodupeerror

最初のバージョンは常に打ち捨てられる。

読み込み中...