スラッシュドット・ジャパン

capra 曰く、

distributed.netのOGR-25プロジェクトで、25マークの最短ゴロム定規が証明された。25マークの最短ゴロム定規の長さは「480」で、マークの配置は以下のとおり。

12-29-39-72-91-146-157-160-161-166-191-207-214-258-290-316-354-372-394-396-431-459-467-480

開始から8年が過ぎたOGR-25プロジェクトには今まで124,387人が貢献してきており、最短解は2007年10月10日に1名と2008年3月24日に1名の合計2名によって発見された。（本家/.記事より）

「最短ゴロム定規」とは、それぞれの差がすべて異なる非負の整数の集合のことで、その集合に含まれる整数の数をマーク数と呼ぶ。たとえば「{0,1,4,6}」は「4マークの最短ゴロム定規」である。ゴロム定規については、「△橘どすこい支所」の「Optimal Golomb Rulerとは？」という記事が分かりやすい。

ゴロム定規は電波望遠鏡や暗号化などで使われているが、最短ゴロム定規を求める問題は効率的な解法が存在せず、NP完全問題である（マーク数が増えると指数的に計算量が増える）ため、マーク数が大きい最短ゴロム定規を求めるのは困難であった。