Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > AUTHORS > A. RAZBOROV:
All reports by Author A. Razborov:

TR97-023 | 3rd June 1997
S. Jukna, A. Razborov, Petr Savicky, Ingo Wegener

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

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 ... more >>>




ISSN 1433-8092 | Imprint