期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2002
卷号：2002
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：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 f can be computed by 3 p -circuits, the function f has nondeterministic BP1s (with one nondeterministic node) of linear size and f has size O ( n 4 ) 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\'y, and Wegener (1999).
f can be computed by 
