__
TR02-033 | 11th June 2002 00:00
__

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

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