Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > CONJUNCTIVE NORMAL FORM:
Reports tagged with conjunctive normal form:

TR02-009 | 17th January 2002
Petr Savicky

On determinism versus unambiquous nondeterminism for decision trees

Let $f$ be a Boolean function. Let $N(f)=\dnf(f)+\dnf(\neg f)$ be the
sum of the minimum number of monomials in a disjunctive normal form
for $f$ and $\neg f$. Let $p(f)$ be the minimum size of a partition
of the Boolean cube into disjoint subcubes such that $f$ is constant on
more >>>




ISSN 1433-8092 | Imprint