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

Beate Bollig

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

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

Abstract

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

How to cite

top

Bollig, 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. [1] M. Ajtai, A non-linear time lower bound for boolean branching programs, in Proc. of 40th FOCS (1999) 60-70. MR1916185
  2. [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. [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. [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. [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. [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. [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. [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. [9] R.E. Bryant, Graph-based algorithms for boolean function manipulation. IEEE Trans. Comput. 35 (1986) 677-691. Zbl0593.94022
  10. [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. [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. [12] J. Hromkovič, Communication Complexity and Parallel Computing. Springer (1997). Zbl0873.68098MR1442518
  13. [13] M. Krause, BDD-based cryptanalysis of keystream generators, in Proc. of EUROCRYT (2002) 222-237. Zbl1055.94018MR1975536
  14. [14] E. Kushilevitz and N. Nisan, Communication Complexity. Cambridge University Press (1997). Zbl0869.68048MR1426129
  15. [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. [16] E.I. Nechiporuk, On a boolean function. Soviet Math. Dokl. 7 (1966) 999-1000. Zbl0161.00901
  17. [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. [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. [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. [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. [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. [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. [23] I. Wegener, The Complexity of boolean Functions. Wiley-Teubner (1987). Zbl0623.94018MR905473
  24. [24] I. Wegener, Branching Programs and Binary Decision Diagrams – Theory and Applications. SIAM Monographs on Discrete Mathematics and Applications (2000). Zbl0956.68068
  25. [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 ?

top

You must be logged in to post comments.

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

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.