Abstract:
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.