The complexity of recognizing graph properties and the evasiveness conjecture

Deciding graph properties—Boolean functions invariant under graph isomorphism—is a foundational challenge in computational complexity. A central question is determining the minimum number of edge queries required to verify such properties in the worst case. A property is evasive if resolving it dema...