Inimizing DNF formulas and ACd0 circuits given a truth table

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

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    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 DNF, and Min-Circuit (also called 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 [31], 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 quasipolynomial 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 extend known hardness results for Min-TCd0 to obtain new hardness results for Min-ACd0, under cryptographic assumptions.

    Original languageEnglish (US)
    Title of host publicationProceedings - Twenty-First Annual IEEE Conference on Computational Complexity, CCC 2006
    Pages237-251
    Number of pages15
    DOIs
    StatePublished - 2006
    Event21st Annual IEEE Conference on Computational Complexity, CCC 2006 - Prague, Czech Republic
    Duration: Jul 16 2006Jul 20 2006

    Publication series

    NameProceedings of the Annual IEEE Conference on Computational Complexity
    Volume2006
    ISSN (Print)1093-0159

    Other

    Other21st Annual IEEE Conference on Computational Complexity, CCC 2006
    CountryCzech Republic
    CityPrague
    Period7/16/067/20/06

    ASJC Scopus subject areas

    • Software
    • Theoretical Computer Science
    • Computational Mathematics

    Fingerprint Dive into the research topics of 'Inimizing DNF formulas and AC<sub>d</sub><sup>0</sup> circuits given a truth table'. Together they form a unique fingerprint.

  • Cite this

    Allender, E., Hellerstein, L., McCabe, P., Pitassi, T., & Saks, M. (2006). Inimizing DNF formulas and ACd0 circuits given a truth table. In Proceedings - Twenty-First Annual IEEE Conference on Computational Complexity, CCC 2006 (pp. 237-251). [1663741] (Proceedings of the Annual IEEE Conference on Computational Complexity; Vol. 2006). https://doi.org/10.1109/CCC.2006.27