Nancy Lynch proved that if a decision problem A is not solvable in polynomial time, then there exists an infinite recursive subset X of its domain on which the decision is almost everywhere complex. General theorems of this kind that can be applied to several well-known automata- based complexity classes, including a common class of randomized algorithms, are proved.