Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR97-023 | 3rd June 1997 00:00

On P versus NP \cap co-NP for Decision Trees and Read-Once Branching Programs


Authors: S. Jukna, A. Razborov, Petr Savicky, Ingo Wegener
Publication: 3rd June 1997 19:01
Downloads: 2005


It is known that if a Boolean function f in n variables
has a DNF and a CNF of size at most N then f also has a
(deterministic) decision tree of size $\exp(O(\log n\log^2 N)$.
We show that this simulation {\em cannot} be made polynomial: we
exhibit explicit Boolean functions f that require deterministic
trees of size $\exp(\Omega(\log^2 N))$ where N is the total
number of monomials in minimal DNFs for f and \neg f. Moreover,
we exhibit new examples of explicit Boolean functions that require
deterministic read-once branching programs of exponential size
whereas both the functions and their negations have small
nondeterministic read-once branching programs. One example results
from the Bruen-Blokhuis bound on the size of nontrivial blocking
sets in projective planes: it is remarkably simple and combinatorially
clear. Whereas other examples have the additional property that f
is in AC^0.

ISSN 1433-8092 | Imprint