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).