# Complexity theoretical results on nondeterministic graph-driven read-once branching programs

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications (2003)

- Volume: 37, Issue: 1, page 51-66
- ISSN: 0988-3754

## Access Full Article

top## Abstract

top## How to cite

topBollig, Beate. "Complexity theoretical results on nondeterministic graph-driven read-once branching programs." RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications 37.1 (2003): 51-66. <http://eudml.org/doc/245590>.

@article{Bollig2003,

abstract = {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).},

author = {Bollig, Beate},

journal = {RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications},

keywords = {computational complexity; read-once branching programs; nondeterminism; lower bounds; Computational complexity},

language = {eng},

number = {1},

pages = {51-66},

publisher = {EDP-Sciences},

title = {Complexity theoretical results on nondeterministic graph-driven read-once branching programs},

url = {http://eudml.org/doc/245590},

volume = {37},

year = {2003},

}

TY - JOUR

AU - Bollig, Beate

TI - Complexity theoretical results on nondeterministic graph-driven read-once branching programs

JO - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

PY - 2003

PB - EDP-Sciences

VL - 37

IS - 1

SP - 51

EP - 66

AB - 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).

LA - eng

KW - computational complexity; read-once branching programs; nondeterminism; lower bounds; Computational complexity

UR - http://eudml.org/doc/245590

ER -

## References

top- [1] M. Ajtai, A non-linear time lower bound for boolean branching programs, in Proc. of 40th FOCS (1999) 60-70. MR1916185
- [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. MR1931815
- [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. Zbl1192.68346MR2121196
- [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. Zbl0992.68057MR1862460
- [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. Zbl1100.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. Zbl1014.68504MR2064452
- [7] A. Borodin, A. Razborov and R. Smolensky, On lower bounds for read-$k$-times branching programs. Comput. Complexity 3 (1993) 1-18. Zbl0777.68043MR1220075
- [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. Zbl0999.68068MR1907013
- [9] R.E. Bryant, Graph-based algorithms for boolean function manipulation. IEEE Trans. Comput. 35 (1986) 677-691. Zbl0593.94022
- [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. Zbl0798.68078MR1244146
- [11] J. Gergov and C. Meinel, Efficient boolean manipulation with OBDDs can be extended to FBDDs. IEEE Trans. Comput. 43 (1994) 1197-1209. Zbl1063.68573
- [12] J. Hromkovič, Communication Complexity and Parallel Computing. Springer (1997). Zbl0873.68098MR1442518
- [13] M. Krause, BDD-based cryptanalysis of keystream generators, in Proc. of EUROCRYT (2002) 222-237. Zbl1055.94018MR1975536
- [14] E. Kushilevitz and N. Nisan, Communication Complexity. Cambridge University Press (1997). Zbl0869.68048MR1426129
- [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.
- [16] E.I. Nechiporuk, On a boolean function. Soviet Math. Dokl. 7 (1966) 999-1000. Zbl0161.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. MR1136069
- [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. Zbl0996.68513MR1844789
- [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. Zbl0947.68056MR1760487
- [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. Zbl0873.68036
- [21] D. Sieling and I. Wegener, A comparison of free BDDs and transformed BDDs. Formal Meth. System Design 19 (2001) 223-236. Zbl1053.68071
- [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. Zbl1006.68054MR1715611
- [23] I. Wegener, The Complexity of boolean Functions. Wiley-Teubner (1987). Zbl0623.94018MR905473
- [24] I. Wegener, Branching Programs and Binary Decision Diagrams – Theory and Applications. SIAM Monographs on Discrete Mathematics and Applications (2000). Zbl0956.68068
- [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. Zbl1054.68554MR2050857

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.