ECCC-Report TR02-033https://eccc.weizmann.ac.il/report/2002/033Comments and Revisions published for TR02-033en-usMon, 17 Jun 2002 12:36:29 +0300
Paper TR02-033
| A very simple function that requires exponential size nondeterministic graph-driven read-once branching programs |
Beate Bollig
https://eccc.weizmann.ac.il/report/2002/033Branching 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).
Mon, 17 Jun 2002 12:36:29 +0300https://eccc.weizmann.ac.il/report/2002/033