A397076 - OEIS

%I #6 Jun 24 2026 21:49:53

%S 1,2,9,184,585803

%N Number of NPN-equivalence classes of Boolean functions of n variables whose deterministic decision-tree complexity D(f) is equal to n.

%C The deterministic decision-tree complexity (deterministic query complexity) D(f) of a Boolean function f is the minimum, over all decision trees computing f, of the tree depth (the worst-case number of input bits queried). We count the NPN-equivalence classes (functions up to negation of input variables, permutation of input variables, and negation of the output) of n-variable Boolean functions with full decision-tree complexity, D(f) = n.

%C a(5) = 585803 was obtained from a complete census of all 616126 NPN classes of Boolean functions on at most 5 variables.

%Y Cf. A000370 (number of NPN-equivalence classes of Boolean functions of n or fewer variables), A397074 (sensitivity), A397075 (degree).

%K nonn,hard,more

%O 1,2

%A _Alex Towell_, Jun 15 2026