ECCC-Report TR97-023https://eccc.weizmann.ac.il/report/1997/023Comments and Revisions published for TR97-023en-usTue, 03 Jun 1997 19:01:03 +0300
Paper TR97-023
| On P versus NP \cap co-NP for Decision Trees and Read-Once Branching Programs |
S. Jukna,
A. Razborov,
Petr Savicky,
Ingo Wegener
https://eccc.weizmann.ac.il/report/1997/023It 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.
Tue, 03 Jun 1997 19:01:03 +0300https://eccc.weizmann.ac.il/report/1997/023