Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR02-033 | 11th June 2002 00:00

A very simple function that requires exponential size nondeterministic graph-driven read-once branching programs

RSS-Feed




TR02-033
Authors: Beate Bollig
Publication: 17th June 2002 12:36
Downloads: 3610
Keywords: 


Abstract:

Branching programs are a well-established computation
model for boolean functions, especially read-once
branching programs (BP1s) have been studied intensively.
A very simple function $f$ in $n^2$ variables is
exhibited such that both the function $f$ and its negation
$\neg f$ can be computed by $\Sigma^3_p$-circuits,
the function $f$ has nondeterministic BP1s
(with one nondeterministic node) of linear size and $\neg f$
has size $O(n^4)$ for oblivious nondeterministic BP1s
but $f$ requires nondeterministic graph-driven BP1s
of size $2^{\Omega(n)}$.
This answers an open question stated by
Jukna, Razborov, Savick\'y, and Wegener (1999).



ISSN 1433-8092 | Imprint