Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with k-term-DNF:
TR05-023 | 16th February 2005
Robert H. Sloan, Balázs Szörényi, György Turán

On k-term DNF with largest number of prime implicants

It is known that a k-term DNF can have at most 2^k ? 1 prime implicants and this bound is sharp. We determine all k-term DNF having the maximal number of prime implicants. It is shown that a DNF is maximal if and only if it corresponds to a non-repeating ... more >>>

ISSN 1433-8092 | Imprint