ملخص: 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 n2 variables is exhibited such that both the function f and its negation ¬f can be computed by 3p-circuits, the function f has nondeterministic BP1s (with one nondeterministic node) of linear size and ¬f has size O(n4) for oblivious nondeterministic BP1s but f requires nondeterministic graph-driven BP1s of size 2(n). This answers an open question stated by Jukna, Razborov, Savick?, and Wegener [Comput. Complexity 8 (1999) 357–370].

لغة: إنجليزية