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

Eric Allender, Lisa Hellerstein, Paul McCabe, Michael Saks

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