TR05-126 Authors: Eric Allender, Lisa Hellerstein, Paul McCabe, Michael Saks

Publication: 5th November 2005 02:20

Downloads: 1662

Keywords:

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

the known reduction of Masek, which is from Circuit-SAT. We then present

a more complex, approximation-preserving reduction, that yields new

inapproximability results for Min-DNF. Finally, we extend known hardness

results for Min-TC0 to obtain new hardness results for Min-AC0, under

cryptographic assumptions.