Complexity Theory of Randomised Testing
本論文は、生成器をチューリング・トランスデューサとしてモデル化することで、効率的かつ空間限定的な入力生成の限界を特徴づけ、生成と決定の複雑性の間の根本的な相違を明らかにし、効率的な生成には特定の証明スキームが必要であり、一般的な論理述語から構成的に導出することはできないことを証明することにより、ランダム化テストに関する初の複雑性理論的基礎を確立するものである。
原論文は CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) でライセンスされています。 これは以下の論文のAI生成解説です。著者が執筆または承認したものではありません。技術的な正確性については原論文を参照してください。 免責事項の全文を読む
あなたは、新しい広大な世界をテストしようとしているゲーム開発者だと想像してください。ゲームがクラッシュしないように、何百万ものランダムなレベル、キャラクター、アイテムを吐き出し、何かが壊れないかを確認できるロボットが必要です。このロボットは「ジェネレーター（生成器）」と呼ばれます。長年、開発者はこれらを手作業で構築し、うまく機能するまで微調整してきました。しかし、誰もこれらのロボットが実際にできることの「理論的な限界」を知りませんでした。彼らは、あらゆる可能なレベルを生成できるのでしょうか？ それとも、役に立つほど速く生成できるのでしょうか？
インペリアル・カレッジ・ロンドンの研究チームとKaihongは、このロボットを複雑性理論（問題の解きやすさを研究する数学）という顕微鏡の下に置くことにしました。彼らは単にコードを見たのではありません。彼らはジェネレーターを「チューリングマシン」（究極の理論上のコンピュータ）としてモデル化し、ランダムなビットのデータを食べてゲームのレベルを吐き出すものとして扱いました。そして、以下の発見をしました。
「作れるもの」のリスト
まず、彼らは問いかけました：ジェネレーターが生成できる絶対的な限界は何でしょうか？
彼らは、もしジェネレーターに無制限の時間とメモリを与えれば、標準的なコンピュータが「認識」できるものと全く同じ集合を生成できることを発見しました。数学の世界では、これは**帰納的に列挙可能（RE）**な言語と呼ばれます。
- 良いニュース: もし入力の集合（例：「すべての有効なCプログラム」）がコンピュータによって認識可能であれば、ジェネレーターは理論上、それらを生成できます。
- 悪いニュース: もし入力の集合が、コンピュータによって認識するには「奇妙すぎる」場合（例：「決して停止しないプログラムのすべて」）、いかなるジェネレーターも決してそれらを生成することはできません。 これはあなたのコードのバグではなく、宇宙の根本的な法則です。すべての無限ループをリストアップできるロボットを作ることはできません。なぜなら、数学的に不可能だからです。
「スピードバンプ（速度低下）」の問題
次に、彼らは問いかけました：もしジェネレーターが高速である必要があるとしたらどうなるでしょうか？ 現実の世界では、テストケースを得るために100万年待つことはできません。数秒で結果が必要です。
研究者たちは、驚くべき事実を発見しました：あるものが有効かどうかを「チェック」できることは、それを「作る」ことができることと同じではありません。
- SATソルバーの例: スイッチの特定の組み合わせによってライトを点灯させるパズルを想像してください。組み合わせが機能するかどうかをチェックするのは困難です（これは「NP完全」です）。しかし、研究者たちは、これらの機能する組み合わせを生成する「速いロボット」を構築できることを示しました。その仕組みは、「証拠（ウィットネス）」を植え付けることです。ロボットは、最初に勝利となる組み合わせを密かに選び、その周囲にパズルを構築します。
- ハッシュ衝突の罠: しかし、彼らはまた、チェックすることが容易であっても、答えを作ることが迅速に行うことは不可能である問題が存在することも証明しました。彼らは「ハッシュ衝突」（異なる入力が同じデジタル指紋を生成すること）を調べました。2つの指紋が一致するかどうかをチェックするのは超高速です。しかし、一致するペアを見つけることは？ もしこれを高速に行うロボットを作れたなら、現代のほぼすべての暗号化のセキュリティを破壊することになるでしょう。
- 結論: 暗号学の世界が破られない限り、「チェックは容易だが、生成は困難」である問題が存在します。 あなたは単に速いジェネレーターを望むだけでは不十分です。数学が、時にはそれを許さないことがあります。
「メモリ」の制約（ファジングとフィードバック）
「ファザー（fuzzer）」と呼ばれる多くの現代的なテストツールは、単にランダムなデータを吐き出すのではなく、以前に試したことを記憶しています。もしテストがプログラムをクラッシュさせたら、ファザーはそれを記憶し、再びクラッシュさせるために入力を微調整しようとします。これは、あらゆる手がかりから学ぶ探偵のようなものです。
研究者たちは、これを限られた**メモリ（空間）**を持つジェネレーターとしてモデル化しました。彼らは、この「メモリ」とフィードバックループがあっても、ジェネレーターには依然として上限があることを発見しました。
- 限界: ジェネレーターが多項式量のメモリを持っている場合（これはほとんどの実用的なツールをカバーします）、それはPSPACEと呼ばれるクラスに属するものしか生成できません。
- 現実的なチェック: これは、最も賢く、メモリを大量に消費するファジングツールであっても、「EXPTIME完全」（指数関数的な時間を要する問題）な問題を生成するための入力を作成することはできないことを意味します。問題がPSPACEマシンで解決できないほど複雑であれば、どれほどのフィードバックやメモリを用いても、ジェネレーターがテストケースを作成することはできません。
「合成可能性」の神話
最後に、彼らはソフトウェアエンジニアの夢に取り組みました：ジェネレーターの「レゴセット」を作れるでしょうか？
例えば、「AとBのためのジェネレーターが欲しい」とか、「NOT Aのためのジェネレーターが欲しい」と言えば、ツールが自動的にそれらを組み合わせて新しい高速なジェネレーターを作成してくれる、というツールです。
論文は、標準的な仮定の下で、この夢に対して明確に**「ノー」**と突きつけています。
- ルール: ジェネレーターを「AND（論理積）」や「NOT（否定）」を使って自動的に組み合わせても、それらが依然として高速であることを保証することはできません。
- 理由: もしこれができれば、現在は高速に解くことが不可能だと信じられている問題を解くことができるからです。
- 例外: 非常に単純で制限されたタイプのロジック（「線形Datalog」や「NL」問題など）については、これを行うことができます。しかし、複雑な「AND」や「NOT」を加えた途端、魔法は解けてしまいます。複雑なルールを組み合わせたい場合は、速度の保証を諦めるか、あるいは運良く成功するまで「試行錯誤（拒絶サンプリング）」を受け入れる必要があります。
総括
論文は、データを生成することは、データが有効かどうかを判定することとは別物であり、しばしばより困難な課題であると結論づけています。
- 証明されたこと: 彼らは、生成可能なものの集合は、まさに帰納的に列挙可能なものの集合であることを証明しました。特定の難しい問題（SATなど）に対する高速なジェネレーターが存在することを証明しましたが、他の問題（暗号が安全であると仮定した場合のハッシュ衝突など）については存在しないことも証明しました。また、フィードバック駆動型のツールはPSPACEによって制限されることも証明しました。
- 否定されたこと: 彼らは、あらゆる論理的組み合わせのルールを扱える、汎用的で高速かつ合成可能なライブラリの可能性を否定しました。また、「チェックが容易」であることが常に「生成が容易」であることを意味するという考えも否定しました。
要するに、テスト用のロボットを作っているなら、単に「速くて賢いもの」を望むだけでは不十分です。数学が境界線を引いています。生成不可能なものがあり、高速に生成することが不可能なものがあり、速度を犠牲にせずに組み合わせることができないものもあります。しかし、今や私たちは、その境界線がどこにあるのかを正確に知ったのです。
自分の分野の論文に埋もれていませんか？
研究キーワードに一致する最新の論文のダイジェストを毎日受け取りましょう——技術要約付き、あなたの言語で。