Comparing the sizes of nondeterministic branching read-k-times programs

DOI10.1016/S0166-218X(02)00305-0MaRDI QIDQ4268146zbMATH OpenFDO

Authors Elizaveta Antonovna Okol'Nishnikova

Publication date 28 October 1999

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/S0166-218X(02)00305-0

zbMATH Keywords

Boolean functionbranching programcomplexity

Mathematics Subject Classification ID

Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Applications of graph theory to circuits and networks (94C15)

Recommendations

• On the hierarchy of nondeterministic branching k-programs
• A note on read-k times branching programs
• scientific article; zbMATH DE number 4047115
• On the hierarchies for deterministic, nondeterministic and probabilistic ordered read-k-times branching programs
• A very simple function that requires exponential size nondeterministic graph-driven read-once branching programs

Cites work

• A note on read-k times branching programs
• scientific article; zbMATH DE number 4172394 (Why is no real title available?)
• scientific article; zbMATH DE number 3121508 (Why is no real title available?)
• scientific article; zbMATH DE number 4045650 (Why is no real title available?)
• scientific article; zbMATH DE number 919281 (Why is no real title available?)
• On lower bounds for read-\(k\)-times branching programs

Cited in

(8)

• A very simple function that requires exponential size nondeterministic graph-driven read-once branching programs
• The power of nondeterminism in polynomial-size bounded-width branching programs
• On the hierarchies for deterministic, nondeterministic and probabilistic ordered read-k-times branching programs
• scientific article; zbMATH DE number 4047115 (Why is no real title available?)
• scientific article; zbMATH DE number 1775455 (Why is no real title available?)
• scientific article; zbMATH DE number 919281 (Why is no real title available?)
• On the hierarchy of nondeterministic branching k-programs
• A note on amortized branching program complexity

This page was built for publication: Comparing the sizes of nondeterministic branching read-k-times programs

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