On the complexity of branching programs and decision trees for clique functions

ABSTRACT

Exponential lower bounds on the complexity of computing the clique functions in the Boolean decision-tree model are proved. For one-time-only branching programs, large polynomial lower bounds are proved for k-clique functions if k is fixed, and exponential lower bounds if k increases with n. Finally, the hierarchy of the classes BPd(P) of all sequences of Boolean functions that may be computed by d-times only branching programs of polynomial size is introduced. It is shown constructively that BP1(P) is a proper subset of BP2(P).

REFERENCES

• 1: M Ajtai , L Babai , P Hajnal , J Komlos , P Pudlak, Two lower bounds for branching programs, Proceedings of the eighteenth annual ACM symposium on Theory of computing, p.30-38, May 28-30, 1986, Berkeley, California, United States [doi>10.1145/12130.12134]
• 2: Allan Borodin , Danny Dolev , Faith E. Fich , Wolfgang Paul, Bounds for width two branching programs, Proceedings of the fifteenth annual ACM symposium on Theory of computing, p.87-93, December 1983 [doi>10.1145/800061.808736]
• 3: Ashok K. Chandra , Merrick L. Furst , Richard J. Lipton, Multi-party protocols, Proceedings of the fifteenth annual ACM symposium on Theory of computing, p.94-99, December 1983 [doi>10.1145/800061.808737]
• 4: Paul E. Dunne, Lower bounds on the complexity of 1-time only branching programs, Fundamentals of Computation Theory, p.90-99, September 09-13, 1985
• 5: ERDOS, P., KLEITMAN, D. J., AND ROTHSCHILD, B.L. Asymptotic enumeration of Kn-free graphs. In Collq. Inter. sulle Teorie Comb. Accad. Naz. Lincei, Rome, 1976, pp. 19-27.
• 6: FURST, M. L., SAXE, J. B., AND SIPSER, M. Parity, circuits, and the polynomial time hierarchy. In Proceedings of the 22nd Annual Foundations of Computer Science. IEEE, New York, 1981, pp. 260-270.
• 7: J Hastad, Almost optimal lower bounds for small depth circuits, Proceedings of the eighteenth annual ACM symposium on Theory of computing, p.6-20, May 28-30, 1986, Berkeley, California, United States [doi>10.1145/12130.12132]
• 8: KRIEGEL, K., AND WAACK, S. Lower bounds on the complexity of real-time branching programs. Tech. Rep. Akademie der Wissenschaften, Berlin, German Democratic Republic.
• 9: MASEK, W. A fast algorithm for the string editing problem and decision graph complexity. M.Sc. thesis, Massachusetts Institute of Technology, Cambridge, Mass., 1976.
• 10: NECHIPORUK, E.I. A Boolean function. Sov. Math. Dokl. 7 (1966), 999-1000.
• 11: Pavel Pudlák, A Lower Bound on Complexity of Branching Programs (Extended Abstract), Proceedings of the Mathematical Foundations of Computer Science 1984, p.480-489, September 03-07, 1984
• 12: PUDL,~K, P., AND Z,~,K, S. Space complexity of computations. Tech. Rep. Univ. Prague, Prague, Czechoslovakia, 1983.
• 13: John E. Savage, The Complexity of Computing, Krieger Publishing Co., Inc., Melbourne, FL, 1987
• 14: Michael Sipser, Borel sets and circuit complexity, Proceedings of the fifteenth annual ACM symposium on Theory of computing, p.61-69, December 1983 [doi>10.1145/800061.808733]
• 15: L. G. Valiant, Exponential lower bounds for restricted monotone circuits, Proceedings of the fifteenth annual ACM symposium on Theory of computing, p.110-117, December 1983 [doi>10.1145/800061.808739]
• 16: WEGENER, I. Optimal decision trees and one-time-only branching programs for symmetric Boolean functions. Inf. Control 62 (1984), 129-143.
• 17: I Wegener, More on the complexity of slice functions, Theoretical Computer Science, v.43 n.2-3, p.201-211, July 1986
• 18: Ingo Wegener, Time-Space trade-offs for branching programs, Journal of Computer and System Sciences, v.32 n.1, p.91-96, Feb. 1986 [doi>10.1016/0022-0000(86)90004-8]
• 19: YAO, A.C. Lower bounds by probabilistic arguments. In Proceedings of the 24th Annual Symposium on Foundations of Computer Science. IEEE, New York, 1983, pp. 420-428.
• 20: Andrew C-C. Yao, Separating the polynomial-time hierarchy by oracles, Proc. 26th annual symposium on Foundations of computer science, p.1-10, October 1985, Portland, Oregon, United States

INDEX TERMS

Primary 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)

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.3 Complexity Measures and Classes
          Subjects: Complexity hierarchies
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Graph algorithms

General Terms:
Algorithms, Theory, Verification