Given a dataset consisting of input/output pairs, how do you find a small DNF consistent with the data? This problem is known as DNF minimization and has appeared in various forms throughout the history of computer science. In this two-part blog post, I’ll survey some results about the complexity of this problem and some connections to learning DNFs.

History and Motivation. DNF minimization has been a central problem in the logic synthesis community for decades. Within this area, the problem is known as “two-level logic synthesis”. It has a rich history going back to a paper written by Quine in 1952 called “The problem of simplifying truth functions“. Quine’s paper was to some extent a response to Shannon’s master’s thesis “A Symbolic Analysis of Relay and Switching Circuits” which introduced Boolean algebra to the study of circuit design. Quine was interested in the following problem. Given a Boolean function (as a truth table), find the smallest DNF for . His algorithm for this task was later refined and improved by McCluskey (McCluskey 1956). Together, their algorithm is known as the Quine-McClusky algorithm for DNF minimzation and is a classic result in logic synthesis.

Practitioners use DNF minimization tools in the VLSI design of PGAs and ASICs. Given its importance, many textbooks in circuit design feature chapters on DNF minimization (see for example Devadas et al. 1994, Hachtel and Somenzi 1996). Unfortunately, the Quine-McClusky algorithm is worst-case exponential time and is too impractical to use in many cases. Instead, practitioners use heuristic algorithms such as ESPRESSO (Rudell and Sangiovanni-Vincentelli 1987). In this blog post, we’ll look at the computational complexity of DNF minimization and give some formal reasons for why its so difficult. For a more thorough survey, including more about the background of the problem, see “Complexity of two-level logic minimization” (2006) by Umans, Villa, and Sangiovanni-Vincentelli.

DNF Minimization given a dataset. In this setting, we are given a dataset of input/output pairs and we would like to output the smallest DNF consistent with . The first hardness result for this problem dates back to Pitt & Valiant in 1988 and leverages hardness of graph coloring.

For every -vertex graph and , there is a dataset such that has a size- DNF if and only if is -colorable.

Pitt & Valiant, 1988

In their paper, Pitt & Valiant phrase their result in terms of learning DNFs rather than minimizing DNFs. These two problems are closely related; we’ll discuss connections to learning in a later post.

The basic idea of the reduction is to take the -vertex graph and encode each edge as an -bit string indicating the vertices in the edge. Each vertex of the graph is similarly encoded with an indicator string. If the graph is -colorable, there is a (monotone) -clause CNF which accepts the edge indicator strings and rejects the vertex indicator strings. It’s not too hard to show the converse also holds. Applying an appropriate transformation to the dataset yields the same result for DNFs.

The best known inapproximability hardness for graph coloring is due to Zuckerman in 2006 which derandomizes a reduction due to Feige & Killian in 1998.

It is -hard to approximate graph coloring on -vertex graphs to within a factor of for all constants .

Zuckerman 2006, Feige & Killian 1998

This result is quite striking. Every graph can trivially be colored using -colors which yields an -approximation. This result says that if you want slightly better approximation, e.g. , the problem becomes -hard.

Any dataset with many 1-inputs can be fit by a DNF of size by creating a unique term for each input. In particular, DNF minimization can be approximated to within a factor of . Using Pitt & Valiant’s reduction and the hardness of graph coloring, we obtain the following corollary which shows that this simple -approximation is essentially the best one can hope for.

It is -hard to approximate DNF minimization within a factor of for all constants .

That’s it for this blog post! In the next one, we’ll discuss DNF minimization given a truth table and some consequences for learning DNFs.

Acknowledgements. I would like to thank my quals committee, Omer Reingold, Aviad Rubinstein and Li-Yang Tan, for valuable feedback and helpful discussions.