Title: Minimization of DNF Formulas Given a Truth Table
Speaker: Lisa Hellerstein, Polytechnic University
Date: March 21, 2006 2:00-3:00pm
Location: DIMACS Center, CoRE Bldg, Room 431, Rutgers University, Busch Campus, Piscataway, NJ
Abstract:
A classical problem in logic minimization is to find the smallest DNF formula consistent with a given truth table. We call this problem minDNF. It is well-known that minDNF is a special case of Set Cover, and that the standard greedy set cover heuristic can be used to obtain an approximate solution to minDNF that is within a factor O(n) of optimal, where n is the number of variables on which the function is defined.
In the 1970's, Masek showed that minDNF is NP-complete. However, few people have taken the time to understand his proof, which consists of a gadget-based reduction from Circuit-SAT. We begin by presenting a new and simpler proof that minDNF is NP-complete, by reduction from 3-Partite Set Cover. We then show that unless NP is contained in quasipolynomial time, there is an absolute constant $\delta < 1$ such that minDNF cannot be approximated to within a factor $O(n^{\delta})$ of optimal.
We also construct an instance of minDNF on which the greedy set cover heuristic produces a solution that is $Omega(n)$ larger than optimal.
The material in this talk is contained in a paper coauthored with Eric Allender, Paul McCabe, Toni Pitassi, and Michael Saks.