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)

Review text

The article is an extended version of the author's paper [\textit{E.~A.~Okol'nishnikova}, On the hierarchy of nondeterministic branching \(k\)-programs, Lect. Notes Comput. Sci. 1279, 376-387 (1997)]. It is shown that, for each natural \(k\), \(k\geq 2\), there exists a sequence of Boolean functions such that the complexity of computing every function of this sequence by nondeterministic branching \(k\)-programs is exponentially larger than that by nondeterministic branching \((k \ln k/ \ln 2+C)\)-programs (with respect to the number of variables of the Boolean function), where \(C\) is a constant independent of \(k\). A result on the same subject for comparing the sizes of nondeterministic branching \(k\)- and \((k+1)\)-programs was obtained by \textit{J.~Thathachar} [On separating the read-\(k\)-times branching program hierarchy, Proc. of the 30th Ann. ACM Symp. on Theory of Computing (1998)].

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)