Abstract A conjecture of Aanderaa and Rosenberg  motivates this work. We investigate the maximum number C( P) of arguments of P that must be tested in order to compute P, a Boolean function of d Boolean arguments. We present evidence for the general conjecture that C( P) = d whenever P(0 d ) ≠ P(1 d ) and P is invariant under a transitive permutation group acting on the arguments. A non-constructive argument (not based on the construction of an “oracle”) settles this question for d a prime power. We use this result to prove the Aanderaa-Rosenberg conjecture: at least v 2 16 entries of the adjacency matrix of a v-vertex undirected graph G must be examined in the worst case to determine if G has any given non-trivial monotone graph property.