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

1, 2, 9, 184, 585803

Offset

1,2

Comments

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.

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

Links

Table of n, a(n) for n=1..5.

Crossrefs

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

Sequence in context: A349691 A078524 A041795 * A123625 A216692 A367901

Adjacent sequences: A397073 A397074 A397075 * A397077 A397078 A397079

Keyword

nonn,hard,more

Author

Alex Towell, Jun 15 2026

Status

approved