Reducibility, randomness, and intractibility (Abstract)

ABSTRACT

The method of showing a problem NP-complete by polynomial reduction is one of the most elegant and productive in our theory ([ 1 ], [ 3 ]). It is a means of providing compelling evidence that a problem in NP is not in P. In this paper we will demonstrate new methods for showing this. Our methods, based on a new notion of reducibility (gamma-reducibility) are apparently of more general applicability than that of polynomial reduction and are intended to be of practical value to researchers in the field. We use our methods to “demonstrate” (i.e., give compelling evidence) that some natural problems in NP which are not known to be NP-complete are, nonetheless, not in P.

REFERENCES

• 1: Stephen A. Cook, The complexity of theorem-proving procedures, Proceedings of the third annual ACM symposium on Theory of computing, p.151-158, May 03-05, 1971, Shaker Heights, Ohio, United States [doi>10.1145/800157.805047]
• 2: John T. Gill, III, Computational complexity of probabilistic Turing machines, Proceedings of the sixth annual ACM symposium on Theory of computing, p.91-95, April 30-May 02, 1974, Seattle, Washington, United States [doi>10.1145/800119.803889]
• 3: Karp, R.M., "Reducibility Among Combinatorial Problems", Complexity of Computer Computations, eds. R.N. Miller and J.W. Thatcher, Plenum Press, 1972, pp.85-104.
• 4: Richard E. Ladner, On the Structure of Polynomial Time Reducibility, Journal of the ACM (JACM), v.22 n.1, p.155-171, Jan. 1975 [doi>10.1145/321864.321877]
• 5: Lipschitz, L., "A Remark on the Diophantine Problem for Addition and Division" to appear.
• 6: Lipschitz, L. private communications.
• 7: Kenneth Manders , Leonard Adleman, NP-complete decision problems for quadratic polynomials, Proceedings of the eighth annual ACM symposium on Theory of computing, p.23-29, May 03-05, 1976, Hershey, Pennsylvania, United States [doi>10.1145/800113.803627]
• 8: Miller, G.L., Riemann's Hypothesis and Tests for Primality, Ph.D. Thesis, Berkeley (1975).
• 9: Plaisted, D.A., "Some Polynomial and Integer Divisibility Problems are NP-hard", Presentation at 17th Annual Symposium on the Foundations of Computer Science, pp. 264-267.
• 10: Pratt, V. "Every Prime has a Succinct Certificate", SIAM J. Comput. 4, 3, pp. 214-220 (Sept. 1975).
• 11: Rabin, M.O., "Probabilistic Algorithms" Algorithms and Complexity, New Directions and Recent Results, Edited by J. Traub, Academic Press.
• 12: Strassen, V. and Solovay, R., "Fast Monte Carlo Tests For Primality" SIAM J. on Computing, to appear.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.3 Complexity Measures and Classes
          Subjects: Reducibility and completeness

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.1 Models of Computation
          Subjects: Bounded-action devices (e.g., Turing machines, random access machines)

  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Probabilistic algorithms (including Monte Carlo)

General Terms:
Algorithms, Measurement, Theory