LLMは45ビットクエリで16枚のカードを識別できるか?
Can LLMs identify 16 cards in 45 bit-queries? (snwagh.com)
要約
本記事は、シャッフルされたカードをバイナリクエリで識別する数学パズルを探求しています。LLMがこのパズル(16枚のカードを対象とし、必要な最小クエリ数に関する未解決問題)の最適な戦略を見つけるためにどのように活用できるかを論じています。著者はLLMエージェントを用いて効率的な解法を模索し、その過程と結果を共有しています。
全文翻訳
LLMは組み合わせ論の問題を解けるか?
LLMと数学研究の交差は、非常に興味深い分野です。数学は客観的で検証可能であり、今日の最先端モデルは数学の概念や手法について広範に学習しています。LLMが、以前は未解決だった(そして実際に難しい)問題を解決するのを見るのは、その能力が驚くほど単純なメカニズムから生まれていることを知りながら、特別な喜びと驚きをもたらします。
私にとって、これは人間の創意工夫、勤勉、そしてエンジニアリングを通じて集団的に達成できることの驚くべき証です。この分野で働く多くの人々と同じように、私も自分自身の視点から、未解決の数学的問題に対するLLMの限界をテストすることに興味を持ちました。この記事は、そのプロセスの物語を語ります。
はじめに
標準的なカードデッキから4枚のカード(ハートのエースとキング、スペードのエースとキング:A♥, K♥, A♠, K♠)があります。カードを指さして、次の2つの質問のうちどちらか1つを尋ねることができます。
- このカードは赤ですか?
- このカードはキングですか?
これらの4枚のカードはシャッフルされています。各カードに1つずつ質問をすることで、どのカードがどれかを特定するのは簡単です(合計8回の質問)。しかし、あなたの目標は、5回以下の質問で常にどのカードがどれかを特定できるような質問戦略を考案することです。以下のインタラクティブメディアで試してみてください。右側から質問をいずれかのカードにドラッグして、そのカードに関する1つの事実を学び、確実に全体の配置がわかったら「I know it!」をクリックしてください。
注 — 敵対的なエンジン このシミュレーターは、各クエリに敵対的に応答します。つまり、固定された隠された順列を明らかにするのではなく、可能な順列を最も多く残すような回答(はい、またはいいえ)を選択します。まさにこれが最悪ケースの境界線を難しくしている理由です。同じクエリを同じ表示されているカードの状態に対して行うと、常に同じ回答が得られるため、決定的または「間違っている」と感じられることがあります。ゲームを探るセクションでは、正直なエンジンとランダムに固定された隠された順列を使用して、より自然な体験を提供します。
24 arrangements left
0 queries used
5 information floor
カード: A♥ K♥ A♠ K♠ — 2つの質問(赤?、キング?)。
目標: 5回以下のクエリで全体の配置を特定する。
質問 · カードにドラッグ
赤のスーツ? (♥♦)
このカードはキングですか?
クエリログ
| Pos | Red? | King? |
|---|
こちらも試してみてください: 8枚カードのバリエーション · 16枚カードのバリエーション
この記事は、この単純なパズルのスケールアップ版で提起された未解決の質問をAIを使用して解決することについてです。記事の残りは以下のセクションに分かれています。
- 16枚カードのパズル は、最初の4枚カードのパズルを16枚に拡張し、未解決の数学的問題 を提示します。
- 大半は最適な戦略の探索 をカバーしています:LLMエージェントの実行セットアップ、50回のイテレーションでパフォーマンスがどのように進化したか、そしてゲームのプレイ可能なブラウザ版(主な結果を見るためにここにジャンプしてください)。
- コラボレーションから得られた主な学び と、最近反証されたドナルド・クヌースによる関連する未解決の予想 とのつながりで締めくくります。
16枚カードのパズル
この小さな問題はより大きな空間に拡張でき、そこで興味深いことが起こります。あなたは16枚のユニークなカード(それぞれが4ビットの値 $0, 1, ext{…}, 15$ をエンコードしている)と4つの二値プロパティを持っています。カードのプロパティ $b$ をチェックすると、1つのビットが得られます:そのカードの隠された値のビット $b$。例えば、プロパティ3はカードの最上位ビット(MSB)を明らかにし、プロパティ0はその最下位ビット(LSB)を明らかにします。
4つのプロパティチェックで任意のカードを完全に特定できることは容易にわかります。ただし、カードはすべて裏向きにシャッフルされているため、どのカードがどれかはわかりません。各プロパティを各カードに対してチェックすれば、64回のチェックでこれを達成できます。パズルは、最悪の場合50回未満のクエリで全体の配置(どのカードがどれか)を復元することです。できますか?(以下のより小さな問題のバリエーションで遊ぶことができます。)
未解決の問題
この物語の根底には、興味深い順列ベースのパズルがあります。隠された順列 $\sigma$ が ${0,\dots,15}$ をスクランブルします。クエリは(カード、プロパティ)のペアを指定し、そのカードの隠された値 $\sigma(\text{card})$ のそのビットを返します。これまでのすべての回答と一致する順列が1つだけになった時点で停止します。$D(16)$ を、事実が許す限り最も役に立たないように各クエリに答える敵対者に対しても常に十分な最小クエリ数とします。私が提起する質問は、$D(16)$ の正確な値は何か?ということです。
$\textbf{情報理論的分析。}$ カウントは下限を設定します。可能な配置は $16!$ 通りあり、各回答は1ビットなので、どの戦略も $D(16) \ge \lceil \log_2 16! \rceil = 45$ を超えることはできません。そして、怠惰な戦略 — 16枚のカードすべての4つのプロパティをチェックする — は $16 \times 4 = 64$ を使用します。真の答えは $[45, 64]$ の間にありますが、どこでしょうか?
形式的な記述と未解決の予想
$n = 2^k$ とし、各値 $0 \le i < n$ をその $k$ ビット文字列 $b(i) \in {0,1}^k$ として書き込みます。順列 $\pi = (\pi_1,\dots,\pi_n)$ は、$E(\pi) = b(\pi_1),b(\pi_2)\cdots b(\pi_n) \in {0,1}^{nk}$ の連結としてエンコードされます。クエリはインデックス $t \in {1,\dots,nk}$ を選択し、$E(\pi)$ の $t$ 番目のビットを返します。$D(n)$ を、最悪の場合(クエリはすべての以前のクエリと回答に依存する可能性があります。つまり、クエリは適応的です)に $\pi$ を一意に識別するために常に十分な最小クエリ数とします。我々は $45 \leq D(16) \leq 64$ であることを知っています。$D(16)$ を決定してください。
未解決の予想: $D(16) = 46$。
なぜこの問題なのか? 適応的で逐次的なパズルの性質は、LLMエージェントの動作方法と自然に対応します:クエリを提案し、回答を観察し、信念を更新し、繰り返します。さらに、独立した研究者として、実際の計算リソースの制約下で(GPUクラスターなし、単一のMacBook、有限のトークン予算)、産業規模の計算なしで意味のある進歩が可能である問題が必要でした。$D(16)$ の計算はこれに適合します:明確に述べられ、客観的に検証可能であり、単一のマシンでの総当たり計算では到達できない範囲にあるため、すべてのアルゴリズム改善が重要になります。
この問題は、さまざまな数学分野に関連する多くの方法で定式化できることに注意してください。適応型ビットクエリ最適決定木として、二部グラフのマッチングとして(これはパーマネント計算に関連しています)、状態空間サイズを削減するための自己同型性として、動的計画法または総当たり探索の周りの戦略として。また、未解決の問題であるにもかかわらず、これをテレンス・タオが提唱した「注意を払わない」問題のカテゴリに分類します。
最適な戦略の探索
最適な戦略の計算には、2つの側面からアプローチしました。まず、手作業で推論できる戦略のセット(各戦略は証明可能な上限)ですが、ペンと紙だけでは限界がありました。次に、主な探求を開始しました:LLMエージェントにメタハーネスで研究ループを実行させ、最良の戦略をひたすら探求させました。このセクションでは、その探求の結果を概説します。検索の前に、注意深い人間が試すであろうことの段階をたどる価値があります(ぜひご自身で試してみてください)– 各戦略は証明可能な上限を与えます。この記事の残りは、AIを使用してこのパズルを試す探求と、その過程で得られた学びについてです。
人間が導き出せる上限
- すべて読む(64回使用)。 4つのプロパティ × 16枚のカード。正しいが、何も活用していない。
- 最後のカードをスキップ(60回使用)。 15枚のカードを完全に特定し、残りの1枚は残ったものとする。 $15 \times 4 = 60$。
- 再帰(49回使用)。 16枚中15枚のカードに対してプロパティ3をチェックし、最後のカードのMSBを推測する。これにより、それぞれ8枚ずつの2つの小さなグループが作成される(15回使用)。それぞれについて、最後のカードを除いたすべてのカードに対してプロパティ2をチェックし、最後のカードを推測する(7+7回使用)。同様に、4つの小さなサブグループに対してプロパティ1をチェックする(3+3+3+3回使用)、そして最後に8つのサブグループのペアの各カードに対してプロパティ0をチェックする(1+1+…+1 = 8回使用)。合計49回使用。
- 人間+コンピュータ(47回使用)。 前述の戦略の改善点。すべてのカードの最上位プロパティを以前と同様にチェックし、8枚のカードの2つのサブ問題に分割する。いくつかの異なる戦略により、$D(8) = 16$ が判明し、これを使用して16枚カードの問題を $15+16+16 = 47$ クエリで完了する。
- エントロピー分割(「20の質問」ゲームのような)が最適に見えるかもしれませんが、8枚カードのゲームでの単純な実験では最適性に達しないことが示されています。しかし、未クエリのブロックに偏りを持たせたエントロピー分割のようなバリアントは、最適な境界に達します。
実行セットアップ
私はメタハーネスを構築し、LLMエージェントに研究ループ自体を実行させました:アイデアを提案し、実装し、実行し、数値を読み取り、次のアイデアを提案する — 数十回のイテレーションにわたって。この探求に不可欠だったルールと制約は以下の通りです。
- リソース制約。 すべての実験は、クラスター/GPUファームなしの単一のMacBookで実行されました。戦略は、単一のボックスが許容できる範囲内でその価値を証明する必要があり、実際、それが問題の頑固さの理由です。最長の実行は、週末(そしてそれ以降)に無人で実行された大規模な網羅的検索でした。
- 1つのアイデア、1つのフォルダ。 すべての試み(
v1,v2, …v50)は、独自のソルバー、検証ツール、およびメモを含む自己完結型のディレクトリです。結果は分離されており、再現可能です。失敗は成功の隣に保持されます。主要な最適化とプログラミング作業のみが、他のディレクトリへの依存関係として引き継がれます。 - 戦略的な誘導。 当初、エージェントは方向性のあるガイダンスと手動の誘導を必要としましたが、適切なハーネスのガードレールにより、これは最終的に減少しました。
エージェントのパフォーマンス対時間
キャンペーン全体を概観します — 後で数値の意味を詳しく説明します。各点はエージェントが試したアイデアです。実線ドットは証明された最悪ケースです — 予算内で完了した網羅的なミニマックス検索です。エラーバーはサンプリングされたヒューリスティックです:1000回のランダムなシャッフルの平均、観測された最悪ケースまでのウィスカーです。太い階段状の線は、各段階で知られている保証された最良の戦略です — 新しい方法が常に優れていると証明された場合にのみステップダウンします。破線は情報フロア、45です。ポイントにカーソルを合わせる(モバイルではタップ)、または← / →を使用します。
物語の形状:階段状の線は、人間が到達可能な戦略(64、60、49、47)を急速に下降し、その後46で停滞します — そこで、正確で構造化されたソルバーが最終的に保証を証明します。ヒューリスティックは典型的なシャッフルではその下に群がっています(平均約44.5)が、それを約束することはできません。平均的に良い戦略を見つけるという独立した問題がありますが、この場合、最悪ケースに焦点を当てました。つまり、特定の境界が十分であることを保証することです。
ゲームを自分で試す
ブラウザで実際のゲームを作成したので、自分で戦略を試すことができます。驚くべきことに — 16枚カードのバリエーションに対する網羅的検索が非常に大規模であったことを考えると — それらのすべてがこの単一のブラウザタブ内に、目立ったパフォーマンスの問題なしに収まります。学習済みポリシー(エキスパートから蒸留された小さなニューラルネットワーク)と、16枚カードゲームの3+1商分解を探求してください。
インタラクティブゲームの使用方法に関する注。
- カードゲームの場合は、非抽象タブを使用してください:プロパティをカードにドラッグしてはい/いいえの質問をするか、戦略を選択して「実行」をクリックします。プロパティがカードを表し、列がプロパティを表す二値グリッド表示の場合は、抽象に切り替えます。8枚、16枚カードのバリエーションには抽象表示をお勧めします。
- ゲームを自分でプレイできます:
- 遊び方(カードゲーム)。 プロパティチップを裏向きのカードにドラッグして1ビットを明らかにします。クエリカウンターが使用回数を追跡します。すべてのカードが特定されると、自動的に表向きになります。「表示」をいつでもクリックして確認できます。戦略メニューからGreedyを選択し、「実行」をクリックしてアルゴリズムのプレイを観察します — スピードスライダーでペースを制御します。
- 遊び方(抽象グリッド)。
?セルをクリックして、そのカードのそのプロパティをチェックします。整合性カウンターは、まだ一致する順列がいくつあるかを示します(パーマネントとしてライブ計算)。それが1に低下すると、すべてのカードが特定されます。
- または、戦略が動作している様子をご覧ください(ゲームのサイズによって戦略は変化します):
- 4枚カード(k=2):
- 自分でプレイ – 手動でプローブします。
- 最適(5) – 情報フロアに正確に一致します。
- 8枚カード(k=3):
- 自分でプレイ。
- 最適決定木(16) – 証明済みで、フロアのすぐ上にあります。
- 固定開始 → 最適(16) – 6回のブラインド、非適応プローブ、その後最適プレイ。
- 再帰 / 層ごとの処理(17) – フロアの1つ上のプローブ。
- 16枚カード(k=4):
- 自分でプレイ。
- 正確なパーマネント貪欲法 – 最も強力なヒューリスティック(典型的な45、最悪ケース46)。
- 学習済みポリシー – 貪欲法を模倣するニューラルネットワークの代替。
- 3+1商分解 – 証明済みの46クエリポリシー。
- MSB分割 – 47クエリのアイデア(2つの8枚カードの半分を解決)。
- 層ごとの処理 – ≤49のベースライン。
- 4枚カード(k=2):
24 arrangements left
0 probes used
5 information floor
Properties · drag to a card
Red suit? (♥♦)
Is this card a King?
Query log
| Pos | Red? | King? |
|---|
Strategy Speed
Drag a property onto any face-down card.
0 probes used
40320 arrangements still possible
16 information floor
Strategy Speed
Click any ? to check that property of that card.
プレイすると、2つのことが際立ちます。第一に、典型的なシャッフルは45クエリをはるかに前に1つの回答に収束します。ここで、フロアは最悪ケースの保証であり、平均ではないことを覚えておくことが役立ちます。第二に、貪欲法は平均的には驚くほど良いですが、最も厄介なシャッフルでは依然として46に陥ります。これが、「45を証明する」のが難しく、「46を証明する」のに週末の検索が必要だった理由全体です。16枚カードゲームのさまざまな戦略(複雑さにもかかわらず、ブラウザで実行されます)をすべて試すことをお勧めします。
LLM支援解決からの学び
ここから得られたいくつかの学びを以下に示します。それぞれにプラス(利点)またはマイナス(限界)のタグが付いています。
-
- 手取り足取りのサポートは薄れ、あなたのハーネスはおそらく次世代モデルやトレーニングデータに組み込まれるでしょう。 このプロジェクトの約50回のイテレーションと、Anthropic Opus 4.5から4.8、OpenAI ChatGPT 5.2から5.6までのフロンティアリリース1年間を通じて、エージェントが必要とする方向性のあるステアリングの量は目に見えて減少しました。初期の頃は、ほぼすべての段階で私が指示する必要がありましたが、終盤には、私が手作業で構築したガードレール(1フォルダにつき1つのアイデア、長時間の実行の前に必須の健全性チェック)が、モデルが自ら行うことが増えました。これは、コンテキストと構造化された知識の保存によってある程度説明できますが、今日モデルの周りに構築する足場が、まさに次世代に吸収される行動であると感じられます。そのため、ハーネスは長期的な資産ではなく、一時的な松葉杖のように感じられます。
-
− エージェントは評価を記述しますが、提案することはめったにありません。 結果への信頼は、評価と健全性チェックから生まれます。エージェントはそれらを記述することには reliably 応じましたが、提案することはほとんどありませんでした。最も重要な方向転換の2つは、トップから来る必要がありました。まず、正確な解決からサンプリングへの移行:エージェントにすべての場所で正確な最悪ケースを追いかけるのをやめさせ、1000回のランダムシャッフルの分布を報告させるには、明示的な指示が必要でした(上のチャートのエラーバー)。第二に、そしてより示唆に富むのは、最適決定木の問題が機械学習のターゲットとして不適切であるということを、それ自体では決して理解しなかったことです。6つの独立したMLトラック(AlphaZeroの自己対戦、適応型MCTS、値関数とGNNの蒸留、エキスパートイテレーション)を試しましたが、すべてが正確なパーマネントポリシーに一致し、1つもそれを上回ることはありませんでした — 1.1 GBのエキスパートを90%以上の忠実度で1 MB未満に蒸留した後でさえ、約10%のエラーフロアで停滞しました。ネットワークがハッシュ関数を学習しようとしているかのようでした(MLは平均的な動作には優れているかもしれませんが、そのような正確な大域的最適解を必要とする問題に対しては構造的に盲目です)。しかし、適切なコンテキスト誘導により、この探求から興味深い戦略が現れました。
-
- 言語選択は制約ではなくなります。 ユーザーが知らない言語で書くことは、この研究スタイルのループではもはや現実的な障壁ではありません。速度が重要であればC++に、メモリ安全性が最も重要であればRustに到達します。これにより、通常は設計上の選択を決定するエンジニアリング上の制約のクラス全体が静かに削除されます。これは、適切な評価とチェックがあれば、実際の言語選択がほとんど重要でなくなる探索的研究にとって特に重要です。
-
− 放置すると探索しますが、探索にはコストがかかります。 解放されたエージェントは、さまざまな深さで多くのことを試み、しばしば最終的に良い答えにたどり着きます — しかし、そのさまよいは高価です。下限の追求 — 「45が不可能であることを証明できるか?」 — は、スラック証明書とデッドステートバリアの1ダース以上のバージョン(v22、v29、v31–v43)にまたがり、フルゲームの正確な解決策は、正直なフレームワークを認める前に、27.85 GB(レイヤーごとに約2.5倍に増加)までフォワードフロンティアを実行しました:これはクラスターか、真に新しい補題を必要とします。各迂回はそれ自体で正当化できましたが、それらが集まると実際の壁時計時間と計算能力を消費しました。したがって、問題は常にエージェントがそこに行けるかどうかではなく、それを見つけるためにそれをさまよわせることが価値があるかどうかかもしれません。多くの場合、より良い動きは、あなた自身の攻撃ラインを持ち、それと協力して問題を解決することです。指示された場合、それは優れた協力者ですが、監視されていない場合は高価な協力者です。
-
− 結果はスケールしますが、洞察は(まだ)スケールしません。 エージェントは結果を生成するのが得意でした。各バージョンには、クリーンで測定可能な「回答」が付属していましたが、洞察を生成するのは著しく苦手でした。攻撃ラインを放棄したとき(たとえば、v32–v33のデッドステートバリア証明)、転移可能な教訓を残すことはめったにありませんでした。むしろ、「これは有望に見えなかった」という漠かな残渣でした。これを手動の研究経験と比較すると、通常は「経験」(XはYで実行するのが難しい、Zは基本的な限界に達する、など)を残します。この非対称性は研究に実際の影響を与える可能性があると推測しています。新しい「結果」の爆発と、「解決済み」と宣言された問題の増加が見られるかもしれませんが、同時に、分野が蓄積する真に新しい洞察の数は静かに減少するでしょう。この感情は、おそらく他の数学者によってよりよく表現されるでしょう。
-
- 明確なターゲットを与えれば、超人的です。 これの最も明確な例はパーマネント(部分状態に対するまだ一貫性のある順列の正確なカウント)であり、この問題の重要なプリミティブでした。一般にパーマネントの計算は#P完全です[7]が、固定サイズ(k=4の16枚カードゲーム)では適切なアルゴリズムがそれを実行可能にし、それがボトルネックになります:1回の貪欲なゲームでさえ、プロジェクトの過程で、PythonリファレンスからC++、手書きのARM NEONおよびx86 SSE4.1ベクトル化グレイコードRyserカーネル、コンポーネントキャッシュを備えたマルチセットDPパーマネント、自己同型性ベースの状態正規化まで、1,000倍以上高速化されました。
-
− フロンティアでは、根拠のない飛躍に注意してください。 特に既知の限界の端では、エージェントは十分に裏付けられていない論理的な飛躍をします。「1のギャップ」が最もクリーンな例です。数回の試みがそれを閉じられなかった後、エージェントは $D(16) = 46$ を確定したものとして扱い、+1ギャップを構造的なものとして扱うようになりました。パターンは本物であり、多くのサブゲームで認定されています — 検索が到達できたすべての残差境界にわたる普遍的な+1 — しかし、「数回試しても勝てなかった」は証明ではなく、完全な45対46の問題は未解決のままです。結果を信頼し、飛躍を検証してください。
クヌースによって当初予想され、2022年にフロリアン・シュトーバーとアルミン・ヴァイスによって反証された、非常に密接に関連する問題がありました[5]。
この問題は、比較ソート(ラジックスソートのような比較を必要としないソートを除く)に関するものです。質問は、n個の要素のグループをソートするために必要な最小比較回数を尋ねます。彼らはこの数を $S(n)$ と呼び、途中の楽しいパズルは $S(4) = 5$ と $S(5) = 7$ を示すことです。一般に、 $S(n)$ には既知の閉形式はありません。最良の一般的なアルゴリズムはマージ挿入ソート(Ford & Johnson, 1959 [2])であり、その比較回数 $F(n)$ は、$n \le 11$ のすべての $n$ に対して情報理論的フロア $\lceil \log_2 n! \rceil$ に正確に一致します — これがクヌースがすべての $n$ に対して最適かもしれないと予想した理由かもしれません[1]。そうではありません。Manacher [3] は、マージ挿入が大きな $n$ では打ち負かされることを示し、カウントフロア自体は $n = 12$ で最初にショートします。ここで $F(12) = 30$ ですが、$\lceil \log_2 12! \rceil = 29$ です。最も小さい真に頑固なケースは $n = 16$ でした:フロアは45、マージ挿入は46を費やし、何十年もの間誰もどちらが正しいかを証明できませんでした。シュトーバーとヴァイスはそれを解決しました — $S(16) = 46$ — 単一のワークステーションでの網羅的な双方向検索を使用し、完全な前方検索のアドバイスとして不完全な後方検索を使用しました[5]。 (その後方アドバイストリックは、私たちの $D(16)$ キャンペーンが見つけた出口標識に最も近いものです。それはまさに v48 が実行するものです。)
ソートは(明白には)私たちの問題ではありません。 一方を他方に還元するのは魅力的です — どちらも同じ $\lceil \log_2 n! \rceil$ カウントフロアに対して、二値の敵対的クエリを通じて $n$ 個のアイテムの隠された順列を識別します。しかし、それらは異なるオブジェクトを扱います。比較ソートは半順序集合上で生きます:各比較は部分順序を洗練し、敵の残りの自由度はそれと一致する線形拡張の数です。私たちのビットクエリゲームは二部互換性上で生きます:各プローブは1つの値の1つの座標を固定し、一貫性のある順列の数は $0/1$ 行列のパーマネントです。一方の問題から他方の問題への境界を伝える対応関係を見つけることができませんでした — 比較は座標の開示ではなく、パーマネントは線形拡張のカウントではありません — そのため、数値的な類似性/接続は、私の知る限り、関連しているが同時に無関係な2つの問題です。誰かがそれらの間に実際の接続を見つけることができれば、それは間違いなく洞察に満ちた新しい数学的作業につながるでしょう。
以下は、両方のシーケンスを共通のフロアに対して示しています。すべての $S(n)$ は既知です。$D(n)$ は $n = 12$ まで解決されており、$n = 13, 14, 15$ では未解決、 $n = 16$ では予想されています。
n
⌈log₂ n!⌉
sorting
bit-query
S(n)
gap
D(n)
gap
2
1
1
0
1
0
3
3
3
0
3
0
4
5
5
0
5
0
5
7
7
0
8
+1
6
10
10
0
11
+1
7
13
13
0
14
+1
8
16
16
0
16
0
9
19
19
0
20
+1
10
22
22
0
24
+2
11
26
26
0
27
+1
12
29
30
+1
31
+2
13
33
34
+1
?
?
14
37
38
+1
?
?
15
41
42
+1
?
?
16
45
46
+1
?
?
緑 = フロアより上のギャップ · 赤 = ソートのギャップと異なるビットクエリのギャップ。解決済みのすべてのDギャップは赤です。未解決の $n = 16$ のエントリが予想通りソートと一致するか、あるいは驚くべきことに45で十分であるかは、現在の問題全体です。
列を下方向に読むと、2つの問題は分かれ、そして再び合流します。ソートはフロアに張り付きます: $S(n)$ は $n \le 11$ のすべての $n$ に対して $\lceil \log_2 n! \rceil$ と等しく、 $n = 12$ で最初にそれを超え、そして有名な $n = 16$ で1プローブ上に留まります。ビットクエリゲームはほとんどすぐにフロアから離れ( $n = 5$ で既に+1ギャップ)、さまよい、 $n = 10$ では+2に達することさえあります。しかし、$n = 8$ ではギャップは0に戻ります。実際、ビットクエリゲームは16未満のすべての2のべき乗($n = 2, 4, 8$)でフロアに正確に一致します。なぜなら、$2^k$ の値は $k$ ビットキューブを無駄なコードワードなしでタイル化し、何も半分しか尋ねられないことはないからです。
その間のさまよいには注意が必要です。$n$ が2のべき乗でない場合、値 ${0, \dots, n-1}$ は $k$ ビットキューブを部分的にしか埋めません:$2^k - n$ 個のコードワードが無駄になるため、そこでのゲームはより不均一で、はるかに非対称であり、そのギャップは根本的なものよりもそのエンコーディングの無駄と絡み合っています。したがって、非2のべき乗ギャップは、クリーンな2のべき乗ケースについてほとんど何も示しません:$n = 10$ での+2は、$n = 16$ について何も示しません。2のべき乗(2、4、8、16)に限定すると、$D$ 列の唯一の正直な読み取りは $0, 0, 0, , ?$ です。
これにより、$n = 16$、次の2のべき乗は、フロア45に正確に一致するように見えるかもしれません(クヌースがおそらくソートについて持っていたのと同じ「きっとここはタイトだろう」という直感)。両方の直感は16で壊れるようです:私が発見した最良の戦略は、$D(16) \leq 46$ という上限を証明しています。これはフロアより1プローブ上です — そしてもしそれが最適なら、それは証明された $S(16) = 46$ を密接に反映しています。私にとって、$D(16)$ が偶然45であるなら、それは非常に驚くべきことです。いずれにせよ、この関係が偶然なのか、それとも私が見つけられなかったより深い数学的接続の影なのかは、この全体の演習が私に残した疑問です。
要約
これまでの問題の簡単な要約です。$D(16)$ は、ビットクエリを使用して順列を一意に識別するために必要な最悪ケースのクエリ数です。
- 証明済み:$45 \leq D(16) \leq 46$
- 証明済み:3+1分解は最悪の場合に正確に46を必要とします。
- 未証明:$D(16)=46$ (代替の未解決問題:完全にインターリーブされた45クエリ戦略が存在するかどうか)。
- 実験的:貪欲法は通常約45で終了しますが、これは保証ではありません。
- 問題に経験的な角度(証明されたXクエリが必要というよりも)からアプローチする興味深いMLベースのアプローチがいくつかあります。
参考文献
- D. E. Knuth. The Art of Computer Programming, Vol. 3: Sorting and Searching (2nd ed.), §5.3.1 (minimum-comparison sorting; the merge-insertion conjecture). Addison-Wesley, 1998.
- L. R. Ford Jr. and S. M. Johnson. “A tournament problem.” The American Mathematical Monthly 66(5): 387–389, 1959. doi:10.2307/2308750
- G. K. Manacher. “The Ford–Johnson sorting algorithm is not optimal.” Journal of the ACM 26(3): 441–456, 1979. doi:10.1145/322139.322145
- M. Peczarski. “The Ford–Johnson algorithm still unbeaten for less than 47 elements.” Information Processing Letters 101(3): 126–128, 2007. doi:10.1016/j.ipl.2006.09.001
- F. Stober and A. Weiß. “Lower bounds for sorting 16, 17, and 18 elements.” arXiv:2206.05597, 2022. Proves $S(16) = 46$. arxiv.org/abs/2206.05597
- H. J. Ryser. Combinatorial Mathematics (Carus Mathematical Monographs 14). Mathematical Association of America, 1963. Ryser’s inclusion–exclusion formula for the permanent – used throughout the interactive game to count consistent arrangements.
- L. G. Valiant. “The complexity of computing the permanent.” Theoretical Computer Science 8(2): 189–201, 1979. Proves computing the permanent is #P-complete. doi:10.1016/0304-3975(79)90044-6
ここにあるすべての数値は、プロジェクト自身のソルバーとゲームプレイヤー(k=4、N=16、情報フロア45)から得られたものです。「証明済み」の点は網羅的なミニマックス結果です。「サンプリング」された点は、観測された最悪ケースを持つ1000回のランダム順列の平均です。チャートとプレイ可能なゲームは静的なクライアントサイドレンダリングです — ブラウザから計算やデータは送信されません。