×

Complexity theoretical results on nondeterministic graph-driven read-once branching programs. (English) Zbl 1084.68049

Summary: Branching programs are a well-established computation model for Boolean functions, especially read-once branching programs (BP1s) have been studied intensively. Recently two restricted nondeterministic (parity) BP1 models, called nondeterministic (parity) graph-driven BP1s and well-structured nondeterministic (parity) graph-driven BP1s, have been investigated. The consistency test for a BP-model \(M\) is the test whether a given BP is really a BP of model \(M\). Here it is proved that the consistency test is co-NP-complete for nondeterministic (parity) graph-driven BP1s. Moreover, a lower bound technique for nondeterministic graph-driven BP1s is presented. The method generalizes a technique for the well-structured model and is applied in order to answer in the affirmative the open question whether the model of nondeterministic graph-driven BP1s is a proper restriction of nondeterministic BP1s (with respect to polynomial size).

MSC:

68Q05 Models of computation (Turing machines, etc.) (MSC2010)
68Q10 Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.)
68Q15 Complexity classes (hierarchies, relations among complexity classes, etc.)
PDFBibTeX XMLCite
Full Text: DOI Numdam EuDML Link

References:

[1] M. Ajtai , A non-linear time lower bound for boolean branching programs , in Proc. of 40th FOCS ( 1999 ) 60 - 70 . MR 1916185
[2] P. Beame , M. Saks , X. Sun and E. Vee , Super-linear time-space tradeoff lower bounds for randomized computation , in Proc. of 41st FOCS ( 2000 ) 169 - 179 . MR 1931815
[3] P. Beame and E. Vee , Time-space trade-offs, multiparty communication complexity, and nearest neighbor problems , in Proc. of 34th STOC ( 2002 ) 688 - 697 . MR 2121196 · Zbl 1192.68346 · doi:10.1145/509907.510006
[4] B. Bollig , Restricted nondeterministic read-once branching programs and an exponential lower bound for integer multiplication . RAIRO: Theoret. Informatics Appl. 35 ( 2001 ) 149 - 162 . Numdam | MR 1862460 | Zbl 0992.68057 · Zbl 0992.68057 · doi:10.1051/ita:2001113
[5] B. Bollig , St. Waack and P. Woelfel , Parity graph-driven read-once branching programs and an exponential lower bound for integer multiplication , in Proc. of 2nd IFIP International Conference on Theoretical Computer Science ( 2002 ) 83 - 94 . · Zbl 1100.68024
[6] B. Bollig and P. Woelfel , A lower bound technique for nondeterministic graph-driven read-once branching programs and its applications , in Proc. of MFCS 2002. Springer, Lecture Notes in Comput. Sci. 2420 ( 2002 ) 131 - 142 . MR 2064452 | Zbl 1014.68504 · Zbl 1014.68504
[7] A. Borodin , A. Razborov and R. Smolensky , On lower bounds for read-\(k\)-times branching programs . Comput. Complexity 3 ( 1993 ) 1 - 18 . MR 1220075 | Zbl 0777.68043 · Zbl 0777.68043 · doi:10.1007/BF01200404
[8] H. Brosenne , M. Homeister and St. Waack , Graph-driven free parity BDDs: Algorithms and lower bounds , in Proc. of MFCS. Springer, Lecture Notes in Comput. Sci. 2136 ( 2001 ) 212 - 223 . MR 1907013 | Zbl 0999.68068 · Zbl 0999.68068
[9] R.E. Bryant , Graph-based algorithms for boolean function manipulation . IEEE Trans. Comput. 35 ( 1986 ) 677 - 691 . Zbl 0593.94022 · Zbl 0593.94022 · doi:10.1109/TC.1986.1676819
[10] J. Gergov and C. Meinel , Frontiers of feasible and probabilistic feasible boolean manipulation with branching programs , in Proc. of STACS. Springer, Lecture Notes in Comput. Sci. 665 ( 1993 ) 576 - 585 . MR 1244146 | Zbl 0798.68078 · Zbl 0798.68078
[11] J. Gergov and C. Meinel , Efficient boolean manipulation with OBDDs can be extended to FBDDs . IEEE Trans. Comput. 43 ( 1994 ) 1197 - 1209 . Zbl 1063.68573 · Zbl 1063.68573 · doi:10.1109/12.324545
[12] J. Hromkovič , Communication Complexity and Parallel Computing . Springer ( 1997 ). MR 1442518 | Zbl 0873.68098 · Zbl 0873.68098
[13] M. Krause , BDD-based cryptanalysis of keystream generators , in Proc. of EUROCRYT ( 2002 ) 222 - 237 . MR 1975536 | Zbl 1055.94018 · Zbl 1055.94018
[14] E. Kushilevitz and N. Nisan , Communication Complexity . Cambridge University Press ( 1997 ). MR 1426129 | Zbl 0869.68048 · Zbl 0869.68048 · doi:10.1017/CBO9780511574948
[15] J. Jain , J. Bitner , D.S. Fussell and J.A. Abraham , Functional partitioning for verification and related problems . Brown/MIT VLSI Conference ( 1992 ) 210 - 226 . · Zbl 0777.94021
[16] E.I. Nechiporuk , On a boolean function . Soviet Math. Dokl. 7 ( 1966 ) 999 - 1000 . Zbl 0161.00901 · Zbl 0161.00901
[17] A.A. Razborov , Lower bounds for deterministic and nondeterministic branching programs , in Proc. of FCT. Springer, Lecture Notes in Comput. Sci. 529 ( 1991 ) 47 - 60 . MR 1136069
[18] P. Savický and D. Sieling , A hierarchy result for read-once branching programs with restricted parity nondeterminism , in Proc. of 25th MFCS. Springer, Lecture Notes in Comput. Sci. 1893 ( 2000 ) 650 - 659 . MR 1844789 | Zbl 0996.68513 · Zbl 0996.68513
[19] P. Savický and S. Žák , A read-once lower bound and a \((1, +k)\)-hierarchy for branching programs . Theoret. Comput. Sci. 238 ( 2000 ) 347 - 362 . MR 1760487 | Zbl 0947.68056 · Zbl 0947.68056 · doi:10.1016/S0304-3975(98)00219-9
[20] D. Sieling and I. Wegener , I . ( 1995 ). Graph driven BDDs - A new data structure for boolean functions. Theoret. Comput. Sci. 141 ( 1995 ) 283 - 310 . Zbl 0873.68036 · Zbl 0873.68036 · doi:10.1016/0304-3975(94)00078-W
[21] D. Sieling and I. Wegener , A comparison of free BDDs and transformed BDDs . Formal Meth. System Design 19 ( 2001 ) 223 - 236 . Zbl 1053.68071 · Zbl 1053.68071 · doi:10.1023/A:1011229414976
[22] J. Thathachar , On separating the read-\(k\)-times branching program hierarchy , in Proc. of 30th Ann. ACM Symposium on Theory of Computing (STOC) ( 1998 ) 653 - 662 . MR 1715611 | Zbl 1006.68054 · Zbl 1006.68054
[23] I. Wegener , The Complexity of boolean Functions . Wiley-Teubner ( 1987 ). MR 905473 | Zbl 0623.94018 · Zbl 0623.94018
[24] I. Wegener , Branching Programs and Binary Decision Diagrams - Theory and Applications . SIAM Monographs on Discrete Mathematics and Applications ( 2000 ). Zbl 0956.68068 · Zbl 0956.68068 · doi:10.1137/1.9780898719789
[25] P. Woelfel , A lower bound technique for restricted branching programs and applications , in Proc. of 19th STACS. Springer, Lecture Notes in Comput. Sci. 2285 ( 2002 ) 431 - 442 . MR 2050857 | Zbl 1054.68554 · Zbl 1054.68554
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.