Hard-core theorems for complexity classes
- 1 January 1985
- journal article
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 32 (1) , 205-217
- https://doi.org/10.1145/2455.214111
Abstract
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.Keywords
This publication has 6 references indexed in Scilit:
- The complexity of promise problems with applications to public-key cryptographyInformation and Control, 1984
- Strong nondeterministic polynomial-time reducibilitiesTheoretical Computer Science, 1982
- Relative complexity of checking and evaluatingInformation Processing Letters, 1976
- On Reducibility to Complex or Sparse SetsJournal of the ACM, 1975
- Recursive Properties of Abstract Complexity ClassesJournal of the ACM, 1972
- An Overview of the Theory of Computational ComplexityJournal of the ACM, 1971