次数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の探索を開始している。
予想よりも、ずっとはやい！ (スコア:3, 参考になる)
2009年から開始した次数27の最短ゴロム定規を探すプロジェクトが2013年現在も進行中であり、予想では7年で発見できるとしている。 [wikipedia.org]
とあるので。
/.jで検索してもスラドが出ないからbingはダメなんだよ
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 次ゴロム定規は最短か?」という判定問題を最短ゴロム定規問題の判定版と考えるのは、最短ゴロム定規問題からこれらの判定問題への多項式チューリング還元が示されない限り、妥当でありません。
「無限に存在」するものを「全て列挙」？ (スコア:0)
そんなことができるのか？
Re: (スコア:0)
最短でないものが一つあればいいんだから。
Re: (スコア:0)
選択公理だ。
Re: (スコア:0)
今回の例でいえば、
これでできるでしょ？
コード化するのも簡単そうだし、分散化するのも容易そう。私はやりたくないけど
Re: (スコア:0)
無限の数を列挙します。それを順に条件を満たすものが出てくるまで調べます。最初に見つけた解がすなわち最小の解です。
というような書き方をすることで、ある種のアルゴリズムを簡潔に記述するテクが有る。
実際には、ライブラリやらインタプリタやらが上手いことやってくれるので、無限の数列なんかは作られず、
順に調べるところで、必要に応じて順に増やしていくような動作になる。
興味深いかなぁ (スコア:0)
探索したくなる人が沢山いるのだから面白いと思う人は結構いるということなんだけど…
これがNP完全なのか証明するとかなら面白いと思うけど
総当たりで探すテーマとしてとっつきやすいから使われてるだけ?
Re:興味深いかなぁ (スコア:2)
ウィキペディア [wikipedia.org]によれば
だそうだから、計算結果には使い道があるらしいよ。これらの応用で「最短」であることにどれほどの意味があるかは知らないけど。
あとは、 1 台の計算機では手に負えなさそうな計算を、地理的にも性能的にもばらばらな計算機の寄り集まりである分散環境で実現できるってのは、計算内容が何であれ、ある意味面白いんじゃない?
Re: (スコア:0)
最も耳障りで美しくない音楽をつくって [gizmodo.jp]人をイラッとさせることができます。
# 最短であることに意味はないけど。
Re: (スコア:0)
数学者が音楽に手を出すより、音楽家が「いラ」っとさせる精度に関しては高いことがわかった。
さすが専門家というべきか。
Re: (スコア:0)
ウィキペディア [wikipedia.org]によれば
だそうだから、計算結果には使い道があるらしいよ。これらの応用で「最短」であることにどれほどの意味があるかは知らないけど。
さすが
Re:興味深いかなぁ (スコア:2)
情報ありがとうございます。それだと、計算結果自体には今のところ特に意味はない、という感じになるのでしょうか (ご存じでしたら)。万一、計算結果から一般の次数 n の最短ゴロム定規について何か規則性が見えてきたら、話はがらっと変わるのでしょうけれど。
Re: (スコア:0)
意味が無いというわけではなくて、すぐに実用に結びつくような結果が出てくるわけでは無いということです（もう実用アレコレのずっと先に到達してしまってる．．．．．）
Re:興味深いかなぁ (スコア:2)
お返事ありがとうございます。 #2553640 で
と書いたのは不適切でした。「計算結果自体には今のところ特に応用先はない」と言いたかったのでした。
Re: (スコア:0)
Bitcoinでも掘ったほうがすぐ金になるだけよっぽどマシだな。