Abstract
Branching programs (b. p.'s) or decision diagrams are a general graph-based model of sequential computation. The b. p.'s of polynomial size are a nonuniform counterpart of LOG. Lower bounds for different kinds of restricted b. p.'s are intensively investigated. An important restriction are so called k-b. p.'s, where each computation reads each input bit at most k times. Although, for more restricted syntactic k-b.p.'s, exponential lower bounds are proven and there is a series of exponential lower bounds for 1-b. p.'s, this is not true for general (nonsyntactic) k-b.p.'s, even for k = 2. Therefore, so called (1, +k)-b. p.'s are investigated. For some explicit functions, exponential lower bounds for (1, +k)-b. p.'s are known. Investigating the syntactic (1,+k)-b. p.'s, Sieling has found functions f n,k which are polvnomially easy for syntactic (1,+k)-b. p.'s, but exponentially hard for syntactic (1,+(k-1))-b. p.'s. In the present paper, a similar hierarchy with respect to k is proven for general (nonsyntactic) (1, +k)-b. p.'s.
The research of both authors was supported by GA of the Czech Republic, grant No. 201/95/0976.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
References
N. Alon, M. B. Nathanson and 1. Z. Ruzsa, The polynomial method and restricted sums of congruence classes, J. Number Theory, to appear.
L. Babai, P. Hajnal, E. Szemeredi and G. Turan, A lower bound for read-once-only branching programs, Journal of Computer and Systems Sciences, vol. 35 (1987), 153–162.
A. Borodin, A. Razborov and R. Smolensky, On Lower Bounds for Read-k-times Branching Programs, Computational Complexity 3 (1993) 1–18.
J. A. Dias da Silva and Y. O. Hamidoune, Cyclic spaces for Grassmann derivatives and additive theory, Bull. London Math. Soc., 26 (1994), 140–146.
P. E. Dunne, Lower bounds on the complexity of one-time-only branching programs, In Proceedings of the FCT, Lecture Notes in Computer Science, 199 (1985), 90–99.
S. Jukna, A Note on Read-k-times Branching Programs, RAIRO Theoretical Informatics and Applications, vol. 29, Nr. 1 (1995), pp. 75–83.
S. Jukna, Entropy of Contact Circuits and Lower Bounds on Their Complexity, Theoretical Computer Science, 57 (1988), pp. 113–129.
S. Jukna, A. A. Razborov, Neither Reading Few Bits Twice nor Reading Illegally Helps Much, TR96-037, ECCC, Trier.
E. A. Okolnishnikova, Lower bounds for branching programs computing characteristic functions of binary codes (in Russian), Metody diskretnogo Analiza, 51 (1991), 61–83.
E. A. Okolnishnikova, Comparing the complexity of binary k-programs (in Russian), Diskretnyj analiz i issledovanije operacij, 1995. Vol. 2, No. 4, pp. 54–73.
S. J. Ponzio, A lower bound for integer multiplication with read-once branching programs, Proceedings of 27 Annual ACM Symposium on the Theory of Computing, Las Vegas, 1995, pp. 130–139.
K. Prachar, Distribution of Prime Numbers (in German), Primzahlverteilung, Springer-Verlag, Berlin-Göttingen-Heidelberg, 1957.
P. Savický, S. žák, A Lower Bound on Branching Programs Reading Some Bits Twice, to appear in TCS.
P. Savický, S. žák, A Large Lower bound for 1-branching programs, TR96-036, ECCC, Trier.
D. Sieling, New Lower Bounds and Hierarchy Results for Restricted Branching Programs, TR 494, 1993, Univ. Dortmund, to appear in J. of Computer and System Sciences.
D. Sieling and I. Wegener, New Lower bounds and hierarchy results for Restricted Branching Programs, in Proc. of Workshop on Graph-Theoretic Concepts in Computer Science WG'94, Lecture Notes in Computer Science Vol. 903 (Springer,Berlin, 1994) 359–370.
J. Simon, M. Szegedy, A New Lower Bound Theorem for Read Only Once Branching Programs and its Applications, Advances in Computational Complexity Theory (J. Cai, editor), DIMACS Series, Vol. 13, AMS (1993) pp. 183–193.
I. Wegener, On the Complexity of Branching Programs and Decision Trees for Clique Functions, JACM 35 (1988) 461–471.
S. žák, An Exponential Lower Bound for One-time-only Branching Programs, in Proc. MFCS'84, Lecture Notes in Computer Science Vol. 176 (Springer, Berlin, 1984) 562–566.
S. žák, A superpolynomial lower bound for (1,+k(n))-branching programs, in Proc. MFCS'95, Lecture Notes in Computer Science Vol. 969 (Springer, Berlin, 1995) 319–325.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1997 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Savický, P., Žák, S. (1997). A hierarchy for (1, +k)-branching programs with respect to k . In: Prívara, I., Ružička, P. (eds) Mathematical Foundations of Computer Science 1997. MFCS 1997. Lecture Notes in Computer Science, vol 1295. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0029991
Download citation
DOI: https://doi.org/10.1007/BFb0029991
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-63437-9
Online ISBN: 978-3-540-69547-9
eBook Packages: Springer Book Archive