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.