Hard-core theorems for complexity classes. (English) Zbl 0632.68047
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.
MSC:
68Q25 | Analysis of algorithms and problem complexity |
68Q05 | Models of computation (Turing machines, etc.) (MSC2010) |
68W99 | Algorithms in computer science |