TY - JOUR

T1 - The complexity of AND—decomposition of Boolean functions

AU - Emelyanov, Pavel

AU - Ponomaryov, Denis

PY - 2020/6/15

Y1 - 2020/6/15

N2 - We consider the complexity of decomposing a Boolean function into a conjunction of components, which may share a (possibly empty) given set of variables Δ. Boolean functions are given as expressions in CNF, DNF, full DNF, and ANF and it is assumed that decomposition components must be in the same normal form as the input expression. We show that deciding decomposability is in general intractable for CNF and DNF already for the empty set of shared variables between the components. On the other hand, we demonstrate that for positive CNF and DNF and full DNF, the finest decomposition components wrt a given Δ can be computed in polynomial time (in the size of the input expression given as a string). The tractability results employ an efficient transformation of input expressions into series of expressions in ANFs aka Boolean polynomials, for which we provide a polynomial time factorization algorithm. Since the reduction leads to solving series of factorization tasks for Boolean polynomials, we discuss a number of ideas on how to optimize massive factorization and report preliminary experimental results.

AB - We consider the complexity of decomposing a Boolean function into a conjunction of components, which may share a (possibly empty) given set of variables Δ. Boolean functions are given as expressions in CNF, DNF, full DNF, and ANF and it is assumed that decomposition components must be in the same normal form as the input expression. We show that deciding decomposability is in general intractable for CNF and DNF already for the empty set of shared variables between the components. On the other hand, we demonstrate that for positive CNF and DNF and full DNF, the finest decomposition components wrt a given Δ can be computed in polynomial time (in the size of the input expression given as a string). The tractability results employ an efficient transformation of input expressions into series of expressions in ANFs aka Boolean polynomials, for which we provide a polynomial time factorization algorithm. Since the reduction leads to solving series of factorization tasks for Boolean polynomials, we discuss a number of ideas on how to optimize massive factorization and report preliminary experimental results.

KW - Computational complexity

KW - Conjunctive decomposition

KW - Disjoint decomposition

KW - Polynomial factorization

UR - http://www.scopus.com/inward/record.url?scp=85069722555&partnerID=8YFLogxK

U2 - 10.1016/j.dam.2019.07.005

DO - 10.1016/j.dam.2019.07.005

M3 - Article

AN - SCOPUS:85069722555

VL - 280

SP - 113

EP - 132

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

SN - 0166-218X

ER -