チリ大学の学部生として、 ベルナルド・スベルカソー コンピューターを使って数学を行うことについて、漠然とした見方をしていました。 それは真の知的発見とは正反対に思えた。

「コンピューターを使って問題を解決することには、本能または直感的な反応があります。たとえば、幻想的な議論の理想的な美しさや優雅さに反するようなものです」と彼は言いました。

しかし、2020 年にスベルカソーは恋に落ち、よくあることですが、優先順位が変わりました。 彼の執着の対象は、彼がオンライン フォーラムで見た質問でした。 彼はほとんどの問題をスキャンして忘れていましたが、これが彼の目に留まりました。 彼は右にスワイプしました。

「私が最初にしたことは、後で誰かが解決策を投稿したときに通知を受け取ることを期待して、Facebook グループの投稿にいいね! をすることでした」と彼は言いました。

問題は、無限のグリッドを数字で埋めることについてでした。 結局のところ、それはひばりで解決できるような問題ではありませんでした。 それを行うために、スベルカソーはカーネギーメロン大学の大学院に行くためにチリを離れなければなりませんでした。

そこで2021年XNUMX月、偶然の出会いを果たした。 マリジン・ヘールは、膨大な計算能力を駆使して難しい数学の問題を解決するコンピューター科学者です。 Subercaseaux は Heule にこの問題を試してみたいかどうか尋ね、コラボレーションを開始しました。 証明 これは 15 という XNUMX つの数字にまとめられます。

可能な限りの方法

2002年には、 ウェイン・ゴダード クレムソン大学の教授と志を同じくする何人かの数学者は、組み合わせ論で問題を吐き出し、特定の制約を与えられたマップの色付けに関する分野の主力の質問に新しいひねりを加えようとしていました.

最終的に彼らは、永遠に続く方眼紙のように、グリッドから始まる問題にたどり着きました。 目標は、数字で埋めることです。 制約が 1 つだけあります。同じ数値が出現する間隔は、数値自体よりも大きくなければなりません。 (距離は、垂直方向と水平方向の間隔を合計することによって測定されます。これは、格子状の都市道路を移動する方法に似ているため、「タクシー」距離として知られる測定基準です。) 1 のペアは、タクシー距離が 2 である隣接するセルを占めることはできません。ただし、距離が XNUMX の直接対角のセルに配置することはできます。

当初、ゴダードと彼の共同研究者は、無限のグリッドを有限の数のセットで埋めることが可能かどうかを知りたがっていました。 しかし、彼と彼のXNUMX人の協力者が この「パッキンの色付け」問題を公開しました ジャーナルで アルス・コンビナトリア 2008 年には、22 個の数を使用して解けることが証明されました。 また、XNUMX つの数字だけでは解けないこともわかっていました。 つまり、問題に対する実際の答え (必要な最小数) は、その中間のどこかにあるということです。

研究者たちは、実際には無限のグリッドを埋めませんでした。 彼らはそうする必要はありませんでした。 代わりに、グリッドの小さなサブセット (10 x 10 の正方形など) を取り、それを数字で埋めて、塗りつぶされたサブセットのコピーを隣り合わせに配置できることを示すだけで十分です。タイルのコピーのある床。

スベルカソーが最初にこの問題を知ったとき、彼はペンと紙を使ってタイルを探し始めました。 彼は数字のグリッドをスケッチし、それらを消して、もう一度やり直しました. 彼はすぐにそのアプローチにうんざりし、友人に、ゲームのマインスイーパに似た Web ベースのツールを設計するように依頼し、組み合わせをより迅速にテストできるようにしました。 さらに数週間の作業の後、彼はグリッドに XNUMX つの数字を詰め込む方法はないと確信しましたが、それ以上のことはできませんでした。さまざまな方法で数字を入力できます。

問題は、後で明らかになるように、グリッドが特定の数のセットでカバーできないことを示すのは、可能であることを示すよりもはるかに難しいことです。 「これは、XNUMX つの方法が機能しないことを示しているだけでなく、考えられるすべての方法が機能しないことを示しています」とゴダード氏は述べています。

Subercaseaux が CMU で働き始め、Heule に彼と一緒に仕事をするよう説得した後、彼らはすぐに 15 の数字でグリッドをカバーする方法を見つけました。 また、12 個の数字だけで問題を解決できる可能性を排除することもできました。 しかし、彼らの勝利の気持ちは短命でした。彼らは、長い間存在していた結果を単に再現しただけであることに気づいたからです.2017年までさかのぼると、研究者は答えが13未満でも15未満でもないことを知っていました. .

著名な教授をペットの問題に取り組ませた大学院 XNUMX 年生にとって、それは不安な発見でした。 「ぞっとしました。 私は基本的に、これに気付かずに問題に数か月取り組んでいました。さらに悪いことに、私はマリジンを作成していました それに時間を無駄にする！」 スベルカソー 書いた ブログ投稿で彼らの仕事を要約しています。

しかし Heule 氏は、過去の結果の発見に元気をもらいました。 それは、他の研究者がその問題を取り組むのに十分重要であると判断したことを示し、得られる価値のある唯一の結果は問題を完全に解決することであることを彼に確認させました.

「この問題に 20 年の歳月が費やされたことがわかると、状況は完全に変わりました」と彼は言いました。

下品な人を避ける

Heule は何年にもわたって、考えられる膨大な組み合わせの中から効率的に検索する方法を見つけることでキャリアを築いてきました。 彼のアプローチは、「満足可能性」の略である SAT 解法と呼ばれています。 ブール式と呼ばれる長い式を作成します。この式は、0 または 1 の 1 つの結果を持つことができます。結果が XNUMX の場合、式は真であり、問​​題は解決されます。

パッキング カラーリングの問題では、式の各変数は、特定のセルが特定の数値で占められているかどうかを表す場合があります。 コンピューターは、式を満たすために変数を割り当てる方法を探します。 コンピューターがそれを実行できる場合、設定した条件でグリッドをパックすることが可能であることがわかります。

残念なことに、パッキング色付け問題をブール式として単純にエンコードすると、何百万もの項に及ぶ可能性があります。コンピューターまたはコンピューターのフリートでさえ、その中で変数を割り当てるさまざまな方法をすべてテストするために無限に実行できます。

「この力ずくでやろうとすると、単純にやると宇宙が終わるまでかかるでしょう」とゴダードは言いました。 「だから、それを可能なものに落とし込むには、いくつかのクールな単純化が必要です。」

さらに、パッキング・カラーリングの問題は、数を追加するたびに、可能な組み合わせが増えるため、約 100 倍難しくなります。 これは、並列に動作するコンピューターのバンクが 12 日分の計算で 100 を除外できる場合、13 を除外するには XNUMX 日の計算時間が必要であることを意味します。

Heule と Subercaseaux は、総当りの計算アプローチをスケールアップすることは、ある意味で下品だと考えていました。 「有望なアイデアがいくつかあったので、『クラスターで 48 時間以内にこの問題を解決できるようになるまで、アプローチを最適化しよう』という考え方を取りました」と Subercaseaux 氏は述べています。

そのためには、コンピューティング クラスターが試行する組み合わせの数を制限する方法を考え出す必要がありました。

「[彼らは] 問題を解決するだけでなく、印象的な方法で解決したいと考えています」と、 アレクサンダー・ソイファー コロラド大学コロラドスプリングス校。

Heule と Subercaseaux は、多くの組み合わせが本質的に同じであることを認識しました。 ひし形のタイルを XNUMX つの異なる数字で埋めようとしている場合、最初に配置する数字が中央の正方形の上に XNUMX つ右に XNUMX つ、または下に XNUMX つ左に XNUMX つ配置しても問題ありません。中央広場。 XNUMX つの配置は互いに対称であり、次の動きをまったく同じように制限するため、両方をチェックする理由はありません。

Heule と Subercaseaux は、コンピューターが対称的な組み合わせを同等のものとして処理できるようにする規則を追加し、合計検索時間を 3 分の 5 に短縮しました。 彼らはまた、 Heule が以前の研究で開発したキューブアンドコンバーと呼ばれる手法を採用しました。これにより、より多くの組み合わせを互いに並行してテストすることができました。 特定のセルに 7、XNUMX、または XNUMX のいずれかが含まれている必要があることがわかっている場合は、問題を分割して、XNUMX つの可能性のそれぞれを異なるコンピューター セットで同時にテストできます。

2022 年 13 月までに、これらの改善により、Heule と Subercaseaux は、14 日未満の計算時間を必要とする実験で、充填色の問題に対する答えとして 15 を除外することができました。 これにより、XNUMX または XNUMX の XNUMX つの可能な答えが残りました。

大きなプラス

14 を除外し、問題を解決するために、Heule と Subercaseaux はコンピューター検索を高速化する別の方法を見つける必要がありました。

最初に、グリッド内の個々のセルに変数を割り当てるブール式を作成しました。 しかし、2022 年 XNUMX 月、彼らは細胞ごとに進める必要がないことに気付きました。 代わりに、プラス記号の形をした XNUMX つのセルで構成される小さな領域を考慮する方が効果的であることを発見しました。

彼らはブール式を書き直して、いくつかの変数が次のような質問を表すようにしました。このプラスの形をした領域のどこかに 7 はありますか? コンピューターは、7 が地域内のどこにあるかを正確に特定する必要はありませんでした。 それがそこにあるかどうかを判断する必要がありました — 答えるのに必要な計算リソースが大幅に少なくてすむ質問です。

「特定の場所ではなくプラスだけを語る変数を持つことは、特定のセルでそれらについて話すよりもはるかに優れていることが判明しました」と Heule 氏は述べています。

プラス検索の効率性に助けられて、Heule と Subercaseaux は 14 年 2022 月のコンピューター実験で 13 を除外しました。これは、XNUMX を除外するために使用したものよりも実行にかかる時間が短くなりました。彼らは次の XNUMX か月を費やして、コンピューターの結論は正しかった — コンピューターが最初にその結論に到達できるようにするために費やした時間とほぼ同じです。

「ランダムなジャーナルで一種の副次的な質問として私たちが生み出したものが、人々のグループを解決する方法を考え出すのに何ヶ月も費やしたと考えるのは喜ばしいことでした」とゴダード氏は述べています。言った。

スベルカソーにとって、これは彼の研究キャリアにおける最初の真の勝利でした。 そして、彼が最初に数学で働くことを考えたときに彼が理想化したタイプの発見ではなかったかもしれませんが、彼は最終的に、それが独自の知的報酬を持っていることを発見しました.

「あなたが黒板をくれて、なぜそれが 15 なのかを示すことができるのは、フォームを理解することではありません」と彼は言いました。 「しかし、問題の制約がどのように機能するか、ここに 6 を配置したり、そこに 7 を配置したりする方がはるかに優れていることを理解することができました。 私たちは多くの直感的な理解を得ました。」