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

44 Scopus citations

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

All Science Journal Classification (ASJC) codes

  • Computer Science(all)
  • Mathematics(all)

Keywords

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

Fingerprint

Dive into the research topics of 'Minimizing disjunctive normal form formulas and AC0 circuits given a truth table'. Together they form a unique fingerprint.

Cite this