2026-07-23T18:08:45Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:603 2024-03-06T11:06:45Z ddc:004 open_access

Approximability of Minimum AND-Circuits Arpe, Jan Manthey, Bodo Optimization problems approximability automated circuit design 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Jan Arpe and Bodo Manthey 2006 Is Part Of Dagstuhl Seminar Proceedings, Volume 6111, Complexity of Boolean Functions (2006) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/DagSemProc.06111.4 urn:nbn:de:0030-drops-6039 https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.06111.4 eng https://creativecommons.org/licenses/by/4.0/legalcode