Abstract
AND-decomposition of a boolean formula means finding two (or several) formulas such that their conjunction is equivalent to the given one. Decomposition is called disjoint if the component formulas do not have variables in common. In the paper, we show that deciding AND-decomposability is intractable for boolean formulas given in CNF or DNF and prove tractability of computing disjoint AND-decomposition components of boolean formulas given in positive DNF, Full DNF, and ANF. The latter result follows from tractability of multilinear polynomial factorization over the finite field of order 2, for which we provide a polytime factorization algorithm based on identity testing for partial derivatives of multilinear polynomials.
Article PDF
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
References
Perkowski, M.A. and Grygiel, S., PSU Electrical Engineering Department Report, Portland, Oregon, USA: Department of Electrical Engineering, Portland State University, 1995.
Steinbach, B. and Lang, C., Artificial Intelligence Review, 2003, vol. 20, p. 319.
Bioch, J.C., in Boolean Models and Methods in Mathematics, Computer Science, and Engineering, Crama, Y. and Hammer, P.L., Eds., New York, NY, USA: Cambridge University Press, 2010, vol. 134 of Encyclopedia of Mathematics and Its Applications, pp. 39–78.
Khatri, S.P. and Gulati, K., Eds., Advanced Techniques in Logic Synthesis, Optimizations and Applications, New York Dordrecht Heidelberg London: Springer, 2011.
Sasao, T. and Butler, J.T., Proc. 2001 Asia and South Pacific Design Automation Conference (ASP-DAC’01), New York, NY, USA: ACM, 2001, pp. 219–224.
Kuon, I., Tessier, R., and Rose, J., FPGA Architecture: Survey and Challenges, Boston-Delft: Now Publishers Inc., 2008.
Mishchenko, A. and Sasao, T., Proc. 40th ACM/IEEE Design Automation Conference (DAC’03), New York, NY, USA: ACM, 2003, pp. 149–154.
Sasao, T. and Besslich, P., IEEE Transactions on Computers, 1990, vol. C-39, p. 262.
Mishchenko, A., Steinbach, B., and Perkowski, M.A., Proc. 38 th ACM/IEEE Design Automation Conference (DAC’01), New York, NY, USA: ACM, 2001, pp. 103–108.
Bengtsson, T., Martinelli, A., and Dubrova, E., Proc. Notes of the 11 th IEEE/ACM International Workshop on Logic & Synthesis (IWLS’02), 2002, pp. 51–55.
Chen, H., Janota, M., and Marques-Silva, J., Proc. Design, Automation & Test in Europe Conference (DATE’12), IEEE, 2012, pp. 816–819.
Choudhury, M. and Mohanram, K., Proc. 2010 IEEE/ACM International Conference on Computer-Aided Design (ICCAD’10), Piscataway, New Jersy, USA: IEEE Press, 2010, pp. 586–591.
Bioch, J.C., Discrete Applied Mathematics, 2005, vol. 149, p. 1.
von zur Gathen, J. and Gerhard, J., Modern Computer Algebra, New York, NY, USA: Cambridge University Press, 2013), 3rd ed.
Shpilka, A. and Volkovich, I., Proc. 37th International Colloquium on Automata, Languages and Programming. Part 1 (ICALP 2010), Springer, 2010, vol. 6198 of Lecture Notes in Computer Science, pp. 408–419.
Ponomaryov, D., Bulletin of the Novosibirsk Computing Center 2008, vol. 28, p. 111, URL http://persons.iis.nsk.su/files/persons/pages/deIta-decomp.pdf.
Morozov, A. and Ponomaryov, D., Siberian Mathematical Journal, 2010, vol. 51, p. 667.
Konev, B., Lutz, C., Ponomaryov, D., and Wolter, F., Proc. Twelfth International Conference on Principles of Knowledge Representation and Reasoning (KR’10), Palo Alto, California, USA: AAAI Press, 2010.
Ponomaryov, D., in Research Note. Abstract appears in Proc. Logic Colloquium’ 14, 2014, URL http://persons.iis.nsk.su/files/persons/pages/sigdecomp.pdf.
Author information
Authors and Affiliations
Corresponding author
Additional information
Original Russian Text © P.G. Emelyanov, D.K. Ponomaryov, 2015, published in Programmirovanie, 2015, Vol. 41, No. 3.
Rights and permissions
About this article
Cite this article
Emelyanov, P.G., Ponomaryov, D.K. Algorithmic issues of AND-decomposition of boolean formulas. Program Comput Soft 41, 162–169 (2015). https://doi.org/10.1134/S0361768815030032
Received:
Published:
Issue Date:
DOI: https://doi.org/10.1134/S0361768815030032