Some connections between nonuniform and uniform complexity classes

ABSTRACT

It is well known that every set in P has small circuits [13]. Adleman [1] has recently proved the stronger result that every set accepted in polynomial time by a randomized Turing machine has small circuits. Both these results are typical of the known relationships between uniform and nonuniform complexity bounds. They obtain a nonuniform upper bound as a consequence of a uniform upper bound. The central theme here is an attempt to explore the converse direction. That is, we wish to understand when nonuniform upper bounds can be used to obtain uniform upper bounds. In this section we will define our basic notion of nonuniform complexity. Then we will show how to relate it to more common notions.

REFERENCES

• 1: L. Adleman, “Two Theorems on Random Polynomial Time,” Proc. 19th IEEE Symp. on Foundations of Computer Science, pp. 75–83 (1978).
• 2: R. Aleliunas, R.M. Karp, R.J. Lipton, L. Lovasz C. Rackoff, “Random Walks, Universal Sequences, and the Complexity of Maze Problems,” Proc. 20th IEEE Symp. on Foundations of Computer Science, (1979).
• 3: A.K. Chandra and L.J. Stockmeyer, “Alternation,” Proc. 17th IEEE Symp. on Foundations of Computer Science, (1976).
• 4: 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]
• 5: S. Fortune, “A Note on Sparse Complete Sets,” SIAM J. Computing 8, pp. 431–433 (1979).
• 6: J. Hartmanis , L. Berman, On isomorphisms and density of NP and other complete sets, Proceedings of the eighth annual ACM symposium on Theory of computing, p.30-40, May 03-05, 1976, Hershey, Pennsylvania, United States [doi>10.1145/800113.803628]
• 7: R.M. Karp, “Reducibility Among Combinatorial Problems,” in Complexity of Computer Computations (R.E. Miller and J.W. Thatcher, eds.), Plenum, New York (1972).
• 8: D. Kozen, “On Parallelism in Turing Machines,” Proc. IEEE Symp. Foundations of Computer Science, (1976).
• 9: A.R. Meyer and M.S. Paterson, “With What Frequency are Apparently Intractable Problems Difficult”, M.I.T. Tech. Report, Feb. 1979.
• 10: A.R. Meyer and L.J. Stockmeyer, “The Equivalence Problem for Regular Expressions with Squaring Requires Exponential Space,” Proc. 13th IEEE Symp. on Switching and Automata Theory, pp. }25;}29 (1972).
• 11: N. Pippenger, “On Simultaneous Resource Bounds,” Proc. 20th IEEE Symp. on Foundations of Computer Science, (}979)
• 12: D.A. Plaisted, “New NP-hard and NP-complete Polynomial and Integer Divisibility Problems,” Proc. 18th IEEE Symp. FOCS, pp. 241–253 (1977).
• 13: J. E. Savage, Computational Work and Time on Finite Machines, Journal of the ACM (JACM), v.19 n.4, p.660-674, Oct. 1972 [doi>10.1145/321724.321731]
• 14: T.S. Schaefer, “On the Complexity of Some Two-Person Perfect-Information Games,” JCSS 16, pp. }85–225 (1978).
• 15: C.P. Schnorr, “Optimal Algorithms for Self-Reducible Problems, 3rd Int. Coll. on Automata, Lang. and Programming, Edinburgh (1976).
• 16: L.J. Stockmeyer, “The Polynomial-Time Heirarchy”, Theoretical Computer Science 3, p. 1–22 (1977).
• 17: L.G. Valiant, “Relative Complexity of Checking and Evaluating, U. of Leeds Tech. Report, 1974.
• 18: L.G. Valiant, “The Complexity of Computing the Permanent,” TCS, (1979)

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.3 Complexity Measures and Classes
          Subjects: Relations among complexity classes

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.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Path and circuit problems

General Terms:
Theory