Evasive Functions:

Any N-bit Boolean function f has a deterministic decision tree complexity associated with it. An N-bit Boolean function is evasive if and only if its deterministic decision tree complexity is N. Some evasive graph properties are connectivity, bipartiteness, is the graph a tree, and does the graph have k edges.

Evasive functions are then the hardest problems in the classical oracle query model; for some input we are required to examine every possible edge. The nonconstant symmetric functions AND, OR, MAJORITY, and PARITY of Section 2.6 are evasive; indeed, all nonconstant symmetric function are evasive (consider two consecutive Hamming weights the function differs on, a and a + 1, the adversary answers 1 to the first a queries, and 0 to the rest).