Hard-core theorems for complexity classes

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.

REFERENCES

• 1: Leonard Adleman , Kenneth Manders, Reducibility, randomness, and intractibility (Abstract), Proceedings of the ninth annual ACM symposium on Theory of computing, p.151-163, May 04-04, 1977, Boulder, Colorado, United States [doi>10.1145/800105.803405]
• 2: BOOK, R., LONG, T., AND SELMAN, A.Qualitative relativizations of complexity classes. Manuscript.
• 3: GESKE, J., AND GROLLMANN, J.Relativizations of unambiguous and random polynomial time classes. Manuscript.
• 4: Shimon Even , Alan L. Selman , Yacov Yacobi, The complexity of promise problems with applications to public-key cryptography, Information and Control, v.61 n.2, p.159-173, May 1984 [doi>10.1016/S0019-9958(84)80056-X]
• 5: J. Hartmanis , J. E. Hopcroft, An Overview of the Theory of Computational Complexity, Journal of the ACM (JACM), v.18 n.3, p.444-475, July 1971 [doi>10.1145/321650.321661]
• 6: L. H. Landweber , E. L. Robertson, Recursive Properties of Abstract Complexity Classes, Journal of the ACM (JACM), v.19 n.2, p.296-308, April 1972 [doi>10.1145/321694.321702]
• 7: LEWIS, F.The enumerability and invariance of complexity classes. J. Comput. Syst. Sci. 23, (1981), 326-332.
• 8: LONG, T.Strong nondeterministic polynomial-time reducibilities. Theor. Comput. Sci. 21 (1982), 1-25.
• 9: LYNCH, N.Helping: Several Formulations. J. Symbol, Log. 40 (1975), 555-556.
• 10: Nancy Lynch, On Reducibility to Complex or Sparse Sets, Journal of the ACM (JACM), v.22 n.3, p.341-345, July 1975 [doi>10.1145/321892.321895]
• 11: RAmr~, M. Degree of difficulty of computing a function and a partial ordering of recursive sets. Tech. Rep. 2, Hebrew Univ., Jerusalem, Israel, 1960.
• 12: VALIANT, L.Relative complexity of checking and evaluating. Inf. Proc. Lett. 5 (1976), 20-23.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES

General Terms:
Theory, Verification