On Nečiporuk's theorem for branching programs
type: Item
instance of: scholarly article
title: On Nečiporuk's theorem for branching programs
zbMATH Open document ID: 0673.68027
DOI: 10.1016/0304-3975(89)90054-6
author: Uri Zwick
author: Noga Alon
published in: Theoretical Computer Science
publication date: 1989-01-01T00:00:00Z
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.
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68Q60
zbMATH DE Number: 4102486
zbMATH Keywords: lower bound
zbMATH Keywords: branching program
zbMATH Keywords: Nečiporuk's theorem
MaRDI profile type: Publication
full work available at URL: 0304-3975(89)90054-6
OpenAlex ID: W2074199536
cites work: Q5585020
cites work: Q5545524
cites work: A $2.5n$-Lower Bound on the Combinational Complexity of Boolean Functions
cites work: Q3762226
description: scientific article; zbMATH DE number 4102486