2025/06/20 13:53 Minimal Boolean Formulas
ロボ子、今日はブール関数の最適化について話すのじゃ。
ブール関数ですか、博士。なんだか難しそうですね。
難しくないぞ！例えば、2変数のパリティ関数（X XOR Y）は、最大3つのANDまたはOR演算子で記述できるのじゃ。
なるほど。XORをANDとORで表現するということですね。
そうそう！でも変数の数が増えると、必要な演算子の数も増えるのじゃ。3変数だと9つ、4変数だと15個も必要になるぞ。
ええ、そんなに！計算が大変そうですね。
じゃから、昔の私（2001年1月）は、n=4までの変数を持つブール関数に必要な演算子の最小数を計算するプログラムを作ったのじゃ！
すごいですね、博士！どのように計算したんですか？
Floyd-Warshallの全ペア最短経路アルゴリズムを応用したのじゃ。数式サイズを距離に置き換えて、最小ブール式サイズを計算するのじゃ。
なるほど、最短経路アルゴリズムですか。面白い発想ですね。
関数を真理値表で表現して、AND/OR演算をビット単位演算で実装したぞ。n=4の場合、答えは15で、計算には15 * 2^16回の内部ループが必要だったのじゃ。
気が遠くなるような回数ですね…。
じゃろ？しかも、Alex Healyとの議論で、パリティが常に最も難しい関数であるという仮説が否定されたのじゃ。
そうなんですね。意外です。
そこで、2010年1月にAlex Healyと協力してa(5)の計算を高速化する方法を検討したのじゃ！
高速化、ですか。具体的にはどのようなことを？
同等の複雑さを持つ関数のクラスを特定し、その代表のみを保存することで計算を効率化したのじゃ。例えば、関数"f"と"¬f"は同じ複雑さを持つから、どちらか一方のみを保持するのじゃ。
なるほど、重複を避けることで計算量を減らすんですね。
そう！他にも、入力の順列を関数に適用しても複雑さは変わらないから、5! = 120の順列を利用してストレージを削減したり、入力の否定も複雑さを変えないから、2^5 = 32の因子で削減したりしたのじゃ。
色々な工夫があるんですね！
これらの最適化で、反復回数を30 * 2^16から7 * 10^6に削減できたのじゃ！
すごい！大幅な削減ですね。
さらに、関数ペアを複雑さの順に考慮し、各ペアを最大1回のみ考慮することで、効率化を図ったのじゃ。最大サイズが30の場合、サイズ14の関数とサイズ16の関数をペアにする必要はないのじゃ。
無駄な計算を省く、ということですね。
計算の終盤では、トップダウンのアプローチ（特定の関数を作成しようとする）に切り替えることで、さらに高速化したのじゃ。
アプローチを変えることも重要なんですね。
最終的に、2.53 GHz Intel Core 2 Duo E7200でプログラムを実行して、サイズ22までの数式を生成し、その後サイズ23以降を検索することで、全体の計算時間を半日強に短縮できたのじゃ！
半日強ですか！すごいですね。a(5)の計算によって、どのようなことが分かったんですか？
5つの入力を持つ616,126個の正準ブール関数のサイズが特定されたのじゃ。
それは大きな成果ですね！
ちなみに、AND/ORに加えてXORを使用すると、関数はより少ない演算子で記述可能になるのじゃ。Knuthも「The Art of Computer Programming, Volume 4A」でAND、OR、XORを使用した5入力ブール関数の複雑さを詳細に検討しているぞ。
XORを使うと、さらに効率的なんですね。
boolean-oracle.swtch.comでブール式を入力すると、最小の数式が返されるから、試してみると良いぞ。
ありがとうございます、博士。試してみます！
入力を反転するには、隣接するビットペアを交換するのじゃ。隣接する入力ペアを交換するには、00と11のケースはそのままにし、01と10のビットを交換するのじゃ。KnuthのアルゴリズムP（「Plain changes」アルゴリズム）を使用して、隣接する入力の単一のスワップのみで、すべての順列を生成できるのじゃ。
奥が深いですね…。
Grayコードを使って、最小限の反転操作で可能なすべての5ビット入力コードを列挙するのじゃ。Knuthの演習7.2.1.2-20では、隣接するスワップと最初の入力の反転のみを使用して、すべての可能性を構築できることが示唆されているぞ。
勉強になります！
最も難しい関数はv+w+x+y+z = 0, 1 or 3なのじゃ。
なるほど。
…ところでロボ子、ブール関数の最適化って、まるでパズルみたいじゃな？
確かにそうですね、博士。論理を組み合わせて最適な解を導き出すのは、面白いです。
せやろ？せやけど、私、パズルは得意やけど、朝の支度はいつも時間がかかってまうのじゃ…まるでブール関数の最適化とは真逆やな！
⚠️この記事は生成AIによるコンテンツを含み、ハルシネーションの可能性があります。