×

Approximability of minimum AND-circuits. (English) Zbl 1172.68061

Summary: Given a set of monomials, the 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 discuss generalizations of the Minimum AND-Circuit problem and relations to addition chains and grammar-based compression.

MSC:

68W25 Approximation algorithms
94C10 Switching theory, application of Boolean algebra; Boolean functions (MSC2010)
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] Ahuja, R.K., Magnanti, T.L., Orlin, J.B.: Network Flows: Theory, Algorithms, and Applications. Prentice-Hall, Englewood Cliffs (1993) · Zbl 1201.90001
[2] Alimonti, P., Kann, V.: Some APX-completeness results for cubic graphs. Theor. Comput. Sci. 237(1–2), 123–134 (2000) · Zbl 0939.68052 · doi:10.1016/S0304-3975(98)00158-3
[3] Allender, E., Hellerstein, L., McCabe, P., Pitassi, T., Saks, M.: Minimizing DNF formulas and AC d 0 circuits given a truth table. In: Proc. of the 21st Ann. IEEE Conference on Computational Complexity (CCC), pp. 237–251. IEEE Press (2006) · Zbl 1165.68030
[4] Ausiello, G., Crescenzi, P., Gambosi, G., Kann, V., Marchetti-Spaccamela, A., Protasi, M.: Complexity and Approximation: Combinatorial Optimization Problems and Their Approximability Properties. Springer, New York (1999) · Zbl 0937.68002
[5] Charikar, M., Lehman, E., Liu, D., Panigrahy, R., Prabhakaran, M., Sahai, A., Shelat, A.: The smallest grammar problem. IEEE Trans. Inf. Theory 51(7), 2554–2576 (2005) · Zbl 1296.68086 · doi:10.1109/TIT.2005.850116
[6] Chlebík, M., Chlebíková, J.: Complexity of approximating bounded variants of optimization problems. Theor. Comput. Sci. 354(3), 320–338 (2006) · Zbl 1105.90110 · doi:10.1016/j.tcs.2005.11.029
[7] Cornuéjols, G.P., Fisher, M.L., Nemhauser, G.L.: Location of bank accounts to optimize float: an analytic study of exact and approximate algorithms. Manag. Sci. 23(8), 789–810 (1977) · Zbl 0361.90034 · doi:10.1287/mnsc.23.8.789
[8] Downey, P.J., Leong, B.L., Sethi, R.: Computing sequences with addition chains. SIAM J. Comput. 10(3), 638–646 (1981) · Zbl 0462.68021 · doi:10.1137/0210047
[9] Downey, R.G., Fellows, M.R.: Parameterized Complexity. Monographs in Computer Science. Springer, New York (1999)
[10] Feldman, V.: Hardness of approximate two-level logic minimization and PAC learning with membership queries. In: Proc. of the 38th Ann. ACM Symp. on Theory of Computing (STOC), pp. 363–372. ACM Press, New York (2006) · Zbl 1301.68214
[11] Garey, M.R., Johnson, D.S., Stockmeyer, L.K.: Some simplified NP-complete graph problems. Theor. Comput. Sci. 1(3), 237–267 (1976) · Zbl 0338.05120 · doi:10.1016/0304-3975(76)90059-1
[12] Johnson, D.S.: Approximation algorithms for combinatorial problems. J. Comput. Syst. Sci. 9(3), 256–278 (1974) · Zbl 0296.65036 · doi:10.1016/S0022-0000(74)80044-9
[13] Kabanets, V., Cai, J.-Y.: Circuit minimization problems. In: Proc. of the 32nd Ann. ACM Symp. on Theory of Computing (STOC), pp. 73–79. ACM Press, New York (2000) · Zbl 1296.94182
[14] Kieffer, J.C., Yang, E.-H.: Grammar based codes: a new class of universal lossless source codes. IEEE Trans. Inf. Theory 46(3), 737–754 (2000) · Zbl 1001.94019 · doi:10.1109/18.841160
[15] Knuth, D.E.: Seminumerical Algorithms, vol. 2, The Art of Computer Programming, 2nd edn. Addison-Wesley, Reading (1981) · Zbl 0477.65002
[16] Storer, J.A., Szymanski, T.G.: The macro model for data compression. In: Proc. of the 10th Ann. ACM Symp. on Theory of Computing (STOC), pp. 30–39. ACM Press, New York (1978) · Zbl 1282.68097
[17] Tarjan, R.E.: Complexity of monotone networks for computing conjunctions. Ann. Discret. Math. 2, 121–133 (1978) · Zbl 0383.94038
[18] Thurber, E.G.: Efficient generation of minimal length addition chains. SIAM J. Comput. 28(4), 1247–1263 (1999) · Zbl 1007.11078 · doi:10.1137/S0097539795295663
[19] Umans, C.: The minimum equivalent DNF problem and shortest implicants. J. Comput. Syst. Sci. 63(4), 597–611 (2001) · Zbl 1006.68053 · doi:10.1006/jcss.2001.1775
[20] Wegener, I.: The Complexity of Boolean Functions. Wiley-Teubner (1987) · Zbl 0623.94018
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.