Math Conjectures

Aanderaa–Karp–Rosenberg Evasiveness Conjecture

OPENMajorConjectureProposed c. 1973 · Standard version

Canonical statement

Fix nn, and let P\mathcal P be a nontrivial property of simple labeled nn-vertex graphs that is invariant under vertex permutations and monotone under adding edges, where nontrivial means that P\mathcal P is neither empty nor the set of all such graphs. Every deterministic algorithm that decides whether an unknown graph has P\mathcal P by adaptively querying edge presence has worst-case query complexity
(n2). \binom n2.
View source LaTeX
Fix \(n\), and let \(\mathcal P\) be a nontrivial property
of simple labeled \(n\)-vertex graphs that is invariant under vertex
permutations and monotone under adding edges, where nontrivial means that
\(\mathcal P\) is neither empty nor the set of all such graphs. Every deterministic
algorithm that decides whether an unknown graph has \(\mathcal P\) by
adaptively querying edge presence has worst-case query complexity
\[
  \binom n2.
\]
TCS-016:[RivestVuillemin1975][KahnSaksSturtevant1984][Miller2013Evasiveness]
Theoretical computer scienceCombinatorics

Notes

The Aanderaa–Karp–Rosenberg conjecture concerns the query complexity of graph properties. An algorithm probes entries of the adjacency matrix of an unknown nn-vertex graph, and the conjecture asserts that every nontrivial graph property that is invariant under vertex relabelling and monotone under adding edges is evasive: any deterministic strategy must, in the worst case, query all (n2)\binom n2 vertex pairs. The modern formulation emerged around 1973, without a single documented first proposal.

Rivest and Vuillemin showed that every such property requires polynomially many queries [RivestVuillemin1975]. The landmark advance is due to Kahn, Saks and Sturtevant, whose topological approach, connecting evasiveness to fixed-point theorems for group actions on simplicial complexes, establishes the full conjecture whenever nn is a prime power [KahnSaksSturtevant1984]. This circle of ideas is developed further in later work on evasiveness and topological fixed-point theorems [Miller2013Evasiveness].

For arbitrary nn the exact all-edges lower bound remains unproved; the conjecture is open, and settling it requires extending the known evasiveness results from prime powers to all values of nn.

References (3)

The boxed statement is the canonical open formulation — not a stronger variant or a related research program. The status reflects the catalog's last review; do your own literature search before investing serious effort.