Are search and decision programs computationally equivalent?

ABSTRACT

From the point of view of sequential polynomial time computation, the answer to the question in the title is 'yes'. The process of self-reducibility is a linear time Turing (oracle) reduction from a given combinatorial search problem to an appropriately defined decision problem. However, from the point of view of fast parallel computation, the answer is not so clear. Many of the sequential algorithms that were 'marked off' as being “inherently sequential” embed within them the self-reducibility process. Can this inherently sequential process be parallelized? To study this problem, we define an abstract setting (namely that of an independence system) in which one, universal search problem captures all combinatorial search problems. We consider several natural decision and function oracles to which this search problem may be reduced. On the positive side, we give efficient probabilistic parallel reductions to these oracles. These reductions constitute a scheme for parallelizing search problems in case the oracles for these problems are themselves efficiently computable in parallel. We give examples of problems that did not yield to parallelism before, but can be parallelized using this scheme. On the negative side, we prove lower bounds on any determininistic parallel reductions to the same oracles. If p processors are used, the sequential (linear) running time cannot be enhanced by more than a factor of &Ogr;(log p) and hence for any polynomial number of processors the problem remains inherently sequential. This proves that randomization can be exponentially more powerful than determinism in our model, and suggests that NC ≠ Random NC. Finally, we state some intriguing conjectures and suggest new directions of research in complexity theory that arise from this work.

REFERENCES

• AIS-84: B. Awerbuch , A. Israeli , Y. Shiloach, Finding euler circuits in logarithmic parallel time, Proceedings of the sixteenth annual ACM symposium on Theory of computing, p.249-257, December 1984 [doi>10.1145/800057.808688]
• BCP-83: A Borodin , S Cook , N Pippenger, Parallel computation for well-endowed rings and space-bounded probabilistic machines, Information and Control, v.58 n.1-3, p.113-136, July/Aug./Sept. 1983 [doi>10.1016/S0019-9958(83)80060-6]
• C-83: S.Cook, "The Classification of Problems which have Fast Parallel Algorithms", Technical Report no. 164/83, Department of Computer Science, University of Toronto, 1983.
• CM-84: S. Cook and P. McKenzie, "The Parallel Complexity of the Abelian Permutation Group Membership Problem", Proc. 24th FOCS, pp. 154-161.
• FRW-84: Faith E. Fich , Prabhakar L. Ragde , Avi Wigderson, Relations between concurrent-write models of parallel computation, Proceedings of the third annual ACM symposium on Principles of distributed computing, p.179-189, August 27-29, 1984, Vancouver, British Columbia, Canada [doi>10.1145/800222.806745]
• G-84: Zvi Galil*, Optimal parallel algorithms for string matching, Proceedings of the sixteenth annual ACM symposium on Theory of computing, p.240-248, December 1984 [doi>10.1145/800057.808687]
• H-84: F. K. Hwang, "Three Versions of a Group Testing Game", SIAM J. Alg. Disc. Methods, 5 no. 2, 1984, pp. 145-153.
• HK-81: D. Hausmann and B. Korte, "On Algorithmic versus Axiomatic Definitions of Matroids", Mathematical Programming Study, 14, 1981, pp. 98-111.
• KUW-84: R M Karp , E Upfal , A Wigderson, Constructing a perfect matching is in random NC, Proceedings of the seventeenth annual ACM symposium on Theory of computing, p.22-32, May 06-08, 1985, Providence, Rhode Island, United States [doi>10.1145/22145.22148]
• KW-84: Richard M. Karp , Avi Wigderson, A fast parallel algorithm for the maximal independent set problem, Proceedings of the sixteenth annual ACM symposium on Theory of computing, p.266-272, December 1984 [doi>10.1145/800057.808690]
• R-83: J. Reif, Parallel Algorithms for Graph Isomorphism", Technical Report no. 14-83, Aiken Computation Lab, Harvard University, 1983.
• S-83: Larry Stockmeyer, The complexity of approximate counting, Proceedings of the fifteenth annual ACM symposium on Theory of computing, p.118-126, December 1983 [doi>10.1145/800061.808740]
• Sa-70: W. J. Savitch, "Relationships between Nondeterministic and Deterministic Space Complexities'', J. Com~ut. System Sci., 4, 1970, pp.177-192.
• TV-84: R. E. Tarjan and U. Vishkin, "Finding Biconnected components and Computing Tree Functions in Logarithmic Parallel Time", Proc. 25th FOCS, 1984, pp. 12-20.
• Va-75: L.G. Valiant, "Parallelism in Comparison Problems", SIAM J. Comput. 4, rio. 3, 1975, pp. 348-355.
• Vi-84: U. Vishkin, "An Efficient Parallel Strong Orientation" Technical Report no. 109 Computer Science Department, New York University, 1984.
• W-76: D. J. A. Welsh, il,latroid Theory, Academic Press, 1976.

INDEX TERMS

Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sorting and searching
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES
      F.4.2 Grammars and Other Rewriting Systems
          Subjects: Decision problems

General Terms:
Algorithms, Theory, Verification