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 is the test whether a given BP is really a BP of model . 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).
Mots clés : computational complexity, read-once branching programs, nondeterminism, lower bounds
@article{ITA_2003__37_1_51_0,
author = {Bollig, Beate},
title = {Complexity theoretical results on nondeterministic graph-driven read-once branching programs},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
pages = {51--66},
publisher = {EDP-Sciences},
volume = {37},
number = {1},
year = {2003},
doi = {10.1051/ita:2003010},
mrnumber = {1991751},
zbl = {1084.68049},
language = {en},
url = {http://www.numdam.org/articles/10.1051/ita:2003010/}
}
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 SP - 51 EP - 66 VL - 37 IS - 1 PB - EDP-Sciences UR - http://www.numdam.org/articles/10.1051/ita:2003010/ DO - 10.1051/ita:2003010 LA - en ID - ITA_2003__37_1_51_0 ER -
%0 Journal Article %A Bollig, Beate %T Complexity theoretical results on nondeterministic graph-driven read-once branching programs %J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications %D 2003 %P 51-66 %V 37 %N 1 %I EDP-Sciences %U http://www.numdam.org/articles/10.1051/ita:2003010/ %R 10.1051/ita:2003010 %G en %F ITA_2003__37_1_51_0
Bollig, Beate. Complexity theoretical results on nondeterministic graph-driven read-once branching programs. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 37 (2003) no. 1, pp. 51-66. doi : 10.1051/ita:2003010. http://www.numdam.org/articles/10.1051/ita:2003010/
[1] , A non-linear time lower bound for boolean branching programs, in Proc. of 40th FOCS (1999) 60-70. | MR
[2] ,, and, Super-linear time-space tradeoff lower bounds for randomized computation, in Proc. of 41st FOCS (2000) 169-179. | MR
[3] and, Time-space trade-offs, multiparty communication complexity, and nearest neighbor problems, in Proc. of 34th STOC (2002) 688-697. | MR
[4] , Restricted nondeterministic read-once branching programs and an exponential lower bound for integer multiplication. RAIRO: Theoret. Informatics Appl. 35 (2001) 149-162. | Numdam | MR | Zbl
[5] , and, 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.
[6] and, 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 | Zbl
[7] , and, On lower bounds for read--times branching programs. Comput. Complexity 3 (1993) 1-18. | MR | Zbl
[8] , and, Graph-driven free parity BDDs: Algorithms and lower bounds, in Proc. of MFCS. Springer, Lecture Notes in Comput. Sci. 2136 (2001) 212-223. | MR | Zbl
[9] , Graph-based algorithms for boolean function manipulation. IEEE Trans. Comput. 35 (1986) 677-691. | Zbl
[10] and, 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 | Zbl
[11] and, Efficient boolean manipulation with OBDDs can be extended to FBDDs. IEEE Trans. Comput. 43 (1994) 1197-1209. | Zbl
[12] , Communication Complexity and Parallel Computing. Springer (1997). | MR | Zbl
[13] , BDD-based cryptanalysis of keystream generators, in Proc. of EUROCRYT (2002) 222-237. | MR | Zbl
[14] and, Communication Complexity. Cambridge University Press (1997). | MR | Zbl
[15] ,, and, Functional partitioning for verification and related problems. Brown/MIT VLSI Conference (1992) 210-226.
[16] , On a boolean function. Soviet Math. Dokl. 7 (1966) 999-1000. | Zbl
[17] , Lower bounds for deterministic and nondeterministic branching programs, in Proc. of FCT. Springer, Lecture Notes in Comput. Sci. 529 (1991) 47-60. | MR
[18] and, 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 | Zbl
[19] and, A read-once lower bound and a -hierarchy for branching programs. Theoret. Comput. Sci. 238 (2000) 347-362. | MR | Zbl
[20] and, I. (1995). Graph driven BDDs - A new data structure for boolean functions. Theoret. Comput. Sci. 141 (1995) 283-310. | Zbl
[21] and, A comparison of free BDDs and transformed BDDs. Formal Meth. System Design 19 (2001) 223-236. | Zbl
[22] , On separating the read--times branching program hierarchy, in Proc. of 30th Ann. ACM Symposium on Theory of Computing (STOC) (1998) 653-662. | MR | Zbl
[23] , The Complexity of boolean Functions. Wiley-Teubner (1987). | MR | Zbl
[24] , Branching Programs and Binary Decision Diagrams - Theory and Applications. SIAM Monographs on Discrete Mathematics and Applications (2000). | Zbl
[25] , 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 | Zbl
Cité par Sources :
