Karp's evasiveness conjecture for monotone graph and digraph properties

Let a graph or digraph property be monotone if it is preserved under deletion of edges or arcs, and let a property be non-trivial if it is neither always true nor always false. A property is evasive if every decision procedure must query all potential edges or arcs. Karp's conjecture. Every non-trivial monotone graph property or digraph property is evasive.

The conjecture strengthens the quadratic Aanderaa--Rosenberg conjecture. The source presents it as a sharpened formulation motivated by counterexamples to Rosenberg's original statement; no resolution is supplied here.