Paper Info
Title
The complexity of AND—decomposition of Boolean functions
Abstract
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.
Year
DOI
Venue
2020
10.1016/j.dam.2019.07.005
Discrete Applied Mathematics
Keywords
DocType
Volume
Conjunctive decomposition,Disjoint decomposition,Polynomial factorization,Computational complexity
Journal
280
ISSN
Citations 
PageRank 
0166-218X
0
0.34
References 
Authors
0
2
Name
Order
Citations
PageRank
Pavel G. Emelyanov1122.48
Denis Ponomaryov2297.43