a generalization and proof of the aanderaa-rosenberg conjecture
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)&equil;d whenever P(0 d ) @@@@ P(1 d ) and P is left invariant by a transitive permutation group acting on the arguments. A non-constructive argument (not based on the construction of an oracle) proves the generalized conjecture for d a prime power. We use this result to prove the Aanderaa-Rosenberg conjecture by showing that at least v 2 /9 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.
general argument order boolean function evidence invariance permutation group power use graph case