A hierarchy result for read-once branching programs with restricted parity nondeterminism

DOI10.1016/J.TCS.2005.03.016MaRDI QIDQ2566039zbMATH OpenOpenAlexFDO

Authors Petr Savický, Detlef Sieling

Publication date 22 September 2005

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2005.03.016

zbMATH Keywords

HierarchyLower bounds on complexityRead-once branching programsRestricted parity nondeterminism

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• scientific article; zbMATH DE number 1759451
• New lower bounds and hierarchy results for restricted branching programs
• A read-once lower bound and a \((1,+k)\)-hierarchy for branching programs
• scientific article; zbMATH DE number 1361505
• Complexity Theoretical Results on Nondeterministic Graph-driven Read-Once Branching Programs

Cites work

• An improved hierarchy result for partitioned BDDs
• Branching Programs and Binary Decision Diagrams
• Complexity theoretical results on partitioned (nondeterministic) binary decision diagrams
• Entropy of contact circuits and lower bounds on their complexity
• Graph-Based Algorithms for Boolean Function Manipulation
• Guess-and-verify versus unrestricted nondeterminism for OBDDs and one-way Turing machines.
• scientific article; zbMATH DE number 3257409 (Why is no real title available?)
• On lower bounds for read-\(k\)-times branching programs
• On P versus NP\(\cap\)co-NP for decision trees and read-once branching programs
• Polynomial size \(\Omega\)-branching programs and their computational power
• Separating the eraser Turing machine classes \(L_ e\), \(NL_ e\), \(co- NL_ e\) and \(P_ e\)
• Time-space trade-off lower bounds for randomized computation of decision problems
• Time-space tradeoffs for branching programs
• Time-space tradeoffs, multiparty communication complexity, and nearest-neighbor problems

Cited in

(9)

• The power of nondeterminism in polynomial-size bounded-width branching programs
• Completeness and non-completeness results with respect to read-once projections
• On the hierarchies for deterministic, nondeterministic and probabilistic ordered read-k-times branching programs
• Lower bounds for restricted read-once parity branching programs
• scientific article; zbMATH DE number 2186831 (Why is no real title available?)
• scientific article; zbMATH DE number 1759451 (Why is no real title available?)
• scientific article; zbMATH DE number 1775455 (Why is no real title available?)
• scientific article; zbMATH DE number 1361505 (Why is no real title available?)
• New lower bounds and hierarchy results for restricted branching programs

This page was built for publication: A hierarchy result for read-once branching programs with restricted parity nondeterminism

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2566039)