Minimizing disjunctive normal form formulas and AC0 circuits given a truth table

Eric Allender, Lisa Hellerstein, Paul Mccabe, Toniann Pitassi, Michael Saks

    Research output: Contribution to journalArticle

    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, which asks whether a given Boolean function presented as a truth table has a k-term disjunctive normal form (DNF), and Min-Circuit (also called the minimum circuit size problem (MCSP)), which asks whether a Boolean function presented as a truth table has a size k Boolean circuit. We present a new reduction proving that Min-DNF is NP-complete. It is significantly simpler than the known reduction of Masek [Some NP-Complete Set Covering Problems, manuscript, 1979], which is from Circuit-SAT. We then give a more complex reduction, yielding the result that Min-DNF cannot be approximated to within a factor smaller than (log N)γ, for some constant γ > 0, assuming that NP is not contained in quasi-polynomial time. The standard greedy algorithm for Set Cover is often used in practice to approximate Min-DNF. The question of whether Min-DNF can be approximated to within a factor of o(log N) remains open, but we construct an instance of Min-DNF on which the solution produced by the greedy algorithm is ω(log N) larger than optimal. Finally, we turn to the question of approximating circuit size for slightly more general classes of circuits. DNF formulas are depth-two circuits of AND and OR gates. Depth-d circuits are denoted by AC0d. We show that it is hard to approximate the size of AC0d. circuits (for large enough d) under cryptographic assumptions.

    Original languageEnglish (US)
    Pages (from-to)63-84
    Number of pages22
    JournalSIAM Journal on Computing
    Volume38
    Issue number1
    DOIs
    StatePublished - 2008

    Keywords

    • Approximation algorithms
    • Complexity theory
    • Machine learning theory
    • Truth table minimization

    ASJC Scopus subject areas

    • Computer Science(all)
    • Mathematics(all)

    Fingerprint Dive into the research topics of 'Minimizing disjunctive normal form formulas and AC<sup>0</sup> circuits given a truth table'. Together they form a unique fingerprint.

    Cite this