Researchers computed that 28 is the minimum number of AND/OR operators needed to represent any Boolean function of five variables. The post details the algorithmic journey from naive brute force (requiring centuries of computation) to sophisticated optimizations using symmetry exploitation, canonical forms, and directed search techniques that reduced runtime to under a day. Key innovations include leveraging function equivalences under permutation and negation, methodical exploration by complexity levels, and switching to targeted search for remaining functions. The work also explores the XOR variant and provides efficient bit manipulation techniques for generating equivalent functions.
Table of contents
A Naive Brute Force ApproachExploiting SymmetryMethodical ExplorationEndgame: Directed SearchAdding XORCode and Web SitePostscript: Generating All Permutations and InversionsSort: