On Nečiporuk's theorem for branching programs

DOI10.1016/0304-3975(89)90054-6MaRDI QIDQ1121017zbMATH OpenOpenAlexFDO

Authors Uri Zwick, Noga Alon

Publication date 1989

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

Full work available at URL https://doi.org/10.1016/0304-3975(89)90054-6

zbMATH Keywords

branching programlower boundNečiporuk's theorem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Specification and verification (program logics, model checking, etc.) (68Q60)

Review text

In 1966 Nečiporuk derived the following lower bound for the minimal size BP(f) of a branching program which computes the Boolean function f: \(BP(f)=\Omega (\sum^{p}_{i=1}(\log r_ i(f))/(\log \log r_ i(f)))\) where \(V_ 1,...,V_ p\) is a partition of the set of variables of f and \(r_ i(f)\) denotes the number of different restrictions of f to \(V_ i.\) Alon and Zwick determine the largest monotone nondecreasing function t for which Nečiporuk's theorem remains true if the above sum is replaced by \(\sum^{p}_{i=1}t(r_ i(f))\). They show t(m)\(\sim (1/2)(\log m)/(\log \log m)\) and derive an explicit formulae for t.

Recommendations

• Nondeterminism and an abstract formulation of Nečiporuk's lower bound method
• Stochastic Algorithms: Foundations and Applications
• scientific article; zbMATH DE number 3913677
• scientific article; zbMATH DE number 5899238
• A lower bound on branching programs reading some bits twice

Cites work

• A 2.5n-Lower Bound on the Combinational Complexity of Boolean Functions
• scientific article; zbMATH DE number 4012495 (Why is no real title available?)
• scientific article; zbMATH DE number 3257409 (Why is no real title available?)
• scientific article; zbMATH DE number 3303654 (Why is no real title available?)

Cited in

(5)

• scientific article; zbMATH DE number 4172394 (Why is no real title available?)
• scientific article; zbMATH DE number 4068271 (Why is no real title available?)
• scientific article; zbMATH DE number 1304312 (Why is no real title available?)
• Nondeterminism and an abstract formulation of Nečiporuk's lower bound method
• Characterization and lower bounds for branching program size using projective dimension

This page was built for publication: On Nečiporuk's theorem for branching programs

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