Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Lisa Hellerstein:

TR05-126 | 5th November 2005
Eric Allender, Lisa Hellerstein, Paul McCabe, Michael Saks

Minimizing DNF Formulas and AC0 Circuits Given a Truth Table

Comments: 2

For circuit classes R, the fundamental computational problem, Min-R,
asks for the minimum R-size of a boolean function presented as a truth
table. Prominent examples of this problem include Min-DNF, and
Min-Circuit (also called MCSP). We begin by presenting a new reduction
proving that Min-DNF is NP-complete. It is significantly ... more >>>

ISSN 1433-8092 | Imprint