Abstract
A syntactic read-k-times branching program has the restriction that no variable occurs more thank times on any path (whether or not consistent) of the branching program. We first extend the result in [31], to show that the “n/2 clique only function”, which is easily seen to be computable by deterministic polynomial size read-twice programs, cannot be computed by nondeterministic polynomial size read-once programs, although its complement can be so computed. We then exhibit an explicit Boolean functionf such that every nondeterministic syntactic read-k-times branching program for computingf has size exp
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
K. Abrahamson, Generalized string matching.SIAM Journal on Computing 16 (1987), 1039–1051.
K. Abrahamson, Time-space tradeoffs for algebraic problems on general sequential machines.JCSS 43 (1991), 269–289.
N. Alon andW. Maass, Meanders and their applications in lower bounds arguments.JCSS 37 (1988), 118–129.
L. Babai, P. Hajnal, E. Szemerédi, andG. Turan, A lower bound for read-once branching programs.JCSS 35 (1987), 153–162.
L. Babai, N. Nisan, and M. Szegedy, Multiparty protocols and logspacehard pseudorandom sequences. InProceedings of the 21st Annual ACM Symposium on Theory of Computing, 1989, 1–11.
L. Babai, P. Pudlák, V. Rödl, andE. Szemerédi, Lower bounds to the complexity of symmetric boolean functions.Theoretical Computer Science 74 (1990), 313–324.
D. Barrington and H. Straubing, Superlinear lower bounds for bounded-width branching programs. In6th Structure in Complexity Theory, 1991, 305–313. To appear inJCSS.
P. Beame, A general sequential time-space tradeoff for finding unique elements.SIAM Journal on Computing 20 (1991), 270–277.
A. Borodin andS. Cook, A time-space tradeoff for sorting on a general sequential model of computation.SIAM Journal on Computing 11 (1982), 287–297.
A. Chandra, M. Furst, and R. Lipton, Multiparty protocols. InProceedings of the 15th Annual ACM Symposium on Theory of Computing, 1983, 94–99.
P.E. Dunne, Lower bounds on the complexity of 1-time only branching programs. InProceedings of the FCT, Lecture Notes in Computer Science, 199, New York, 1985, Springer-Verlag, 90–99.
M.A. Gavrilov,The Theory of Relay and Switching Circuits. Nauka, 1950. In Russian.
N. Immerman, Nondeterministic space is closed under complementation.SIAM J. Comput. 17 (1988), 935–938.
N. Jacobson,Basic Algebra I. W.H. Freeman and Company, New York, second edition, 1985.
S. Jukna,A Note on Read-k Times Branching Programs. Technical Report 448, Universität Dortmund, 1992.
M. Krause, C. Meinel, and S. Waack, Separating complexity classes related to certain input oblivious logarithmic space bounded Turing machines. In4th Structure in Complexity Theory Conference, 1989, 240–259.
M. Krause, C. Meinel, andS. Waack, Separating the eraser turing machine classesL e ,N L e ,co-N L e andP e .Theoretical Computer Science 86 (1991), 267–275.
C. Y. Lee, Representation of switching cirucits by binary-decision programs.Bell System Technical Journal 38 (1959), 985–999.
Y. Mansour, N. Nisan, and P. Tiwari, The computational complexity of universal hashing. InProceedings of the 22nd Annual ACM Symposium on the Theory of Computing, 1990, 235–243.
W. Masek,A Fast Algorithm for the String Editing Problem and Decision Graph Complexity. M.Sc. Thesis, Massachusetts Institute of Technology, Cambridge, 1976.
E. A. Okolnishnikova, Lower bounds for branching programs computing characteristic functions of binary codes.Metody discretnogo analiza 51 (1991), 61–83, In Russian.
C. H. Papadimitriou andM. Sipser, Communication complexity.JCSS 28 (1984), 260–269.
P. Pudlák, On bounded depth circuits with arbitrary gates. Preprint.
A. Razborov, Lower bounds for deterministic and nondeterministic branching programs. InProceedings of the 8th FCT, Lecture Notes in Computer Science, 529, New York/Berlin, 1991, Springer-Verlag, 47–60.
W. J. Savitch, Relationships between nondeterministic and deterministic tape complexities.JCSS 4 (1970), 177–192.
C. Shannon, A symbolic analysis of relay and switching networks.Transactions of American Institute of Electrical Engineers 57 (1938), 713–723.
J. Simon and M. Szegedy, Lower bound techniques for read only once branching programs. Preprint, 1990.
R. Szelepcsényi, The method of forcing for nondeterministic automata.Bull. European Assoc. Theoret. Comput. Sci. 33 (1987), 96–100.
I. Wegener,The Complexity of Boolean Functions. Wiley-Teubner Series in Comp. Sci., New York/Stuttgart, 1987.
Y. Yesha, Time-space tradeoffs for matrix multiplication and the discrete Fourier transform on any general sequential random-access computer.SIAM Journal on Computing 29 (1984), 183–197.
S. Žák, An exponential lower bound for one-time-only branching programs. InProceedings of the 11th MFCT, Lecture Notes in Computer Science, 176, New York/Berlin, 1984, Springer-Verlag, 562–566.