nx_boolsynth.nx

nx_boolsynth.nx -- a NEW search space: minimal straight-line BOOLEAN circuits for a 3-input function, where verification is EXACT and free. The trick: drive the inputs with the truth-table columns a=0xAA, b=0xCC, c=0xF0 (the 8 bit positions enumerate all 8 input combinations in parallel), so a program's output BYTE *is* its truth table. A candidate matches the target iff (output & 0xFF) == target -- one word op covers ALL inputs, no execution, no loop. Iterative deepening over op count gives the PROVABLY-MINIMAL circuit over {AND, OR, XOR, NOT}. This is the class where exhaustive search can beat a heuristic compiler (the compiler emits the literal expression; the superoptimizer finds the floor). license_tier: ORIGINAL Refs: Knuth TAOCP 4A 7.1.2 (boolean evaluation); STOKE; souper.