Hard-core theorems for complexity classes
Shimon Even, Alan L. Selmen, Yacov Yacobi · Journal of the ACM · 1985
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. In this paper, 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.