Approximability of Minimum AND-Circuits

Abstract

Given a set of monomials, the {sc Minimum AND-Circuit} problem asks for a circuit that computes these monomials using AND-gates of fan-in two and being of minimum size. 

We prove that the problem is not polynomial time approximable within a factor of less than $1.0051$ unless $mathsf{P} = mathsf{NP}$, even if the monomials are restricted to be of degree at most three. For the latter case, we devise several efficient approximation algorithms, yielding an approximation ratio of $1.278$. For the general problem, we achieve an approximation ratio of $d-3/2$, where $d$ is the degree of the largest monomial. 

In addition, we prove that the problem is fixed parameter tractable with the number of monomials as parameter. Finally, we reveal connections between the {sc Minimum AND-Circuit} problem and several problems from different areas.