Complexity Theoretical Results on Nondeterministic Graph-driven Read-Once Branching Programs

Beate Bollig

RAIRO - Theoretical Informatics and Applications (2010)

  • 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 37.1 (2010): 51-66. <http://eudml.org/doc/92713>.

@article{Bollig2010,
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},
keywords = {Computational complexity; read-once branching programs; nondeterminism; lower bounds.; lower bounds},
language = {eng},
month = {3},
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/92713},
volume = {37},
year = {2010},
}

TY - JOUR
AU - Bollig, Beate
TI - Complexity Theoretical Results on Nondeterministic Graph-driven Read-Once Branching Programs
JO - RAIRO - Theoretical Informatics and Applications
DA - 2010/3//
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.; lower bounds
UR - http://eudml.org/doc/92713
ER -

References

top
  1. M. Ajtai, A non-linear time lower bound for boolean branching programs, in Proc. of 40th FOCS (1999) 60-70.  
  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.  
  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.  
  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.  
  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.  
  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.  
  7. A. Borodin, A. Razborov and R. Smolensky, On lower bounds for read-k-times branching programs. Comput. Complexity3 (1993) 1-18.  
  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.  
  9. R.E. Bryant, Graph-based algorithms for boolean function manipulation. IEEE Trans. Comput.35 (1986) 677-691.  
  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.  
  11. J. Gergov and C. Meinel, Efficient boolean manipulation with OBDDs can be extended to FBDDs. IEEE Trans. Comput.43 (1994) 1197-1209.  
  12. J. Hromkovic, Communication Complexity and Parallel Computing. Springer (1997).  
  13. M. Krause, BDD-based cryptanalysis of keystream generators, in Proc. of EUROCRYT (2002) 222-237.  
  14. E. Kushilevitz and N. Nisan, Communication Complexity. Cambridge University Press (1997).  
  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.  
  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.  
  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.  
  19. P. Savický and S. Zák, A read-once lower bound and a (1, +k)-hierarchy for branching programs. Theoret. Comput. Sci.238 (2000) 347-362.  
  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.  
  21. D. Sieling and I. Wegener, A comparison of free BDDs and transformed BDDs. Formal Meth. System Design19 (2001) 223-236.  
  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.  
  23. I. Wegener, The Complexity of boolean Functions. Wiley-Teubner (1987).  
  24. I. Wegener, Branching Programs and Binary Decision Diagrams - Theory and Applications. SIAM Monographs on Discrete Mathematics and Applications (2000).  
  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.  

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.