Name
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. |
Year | DOI | Venue |
|---|---|---|
2015 | 10.1134/S0361768815030032 | Programming and Computer Software |
Keywords | Field | DocType |
Boolean Function, Variable Partition, Symbol Sequence, Boolean Formula, Algorithmic Issue | Boolean function,Discrete mathematics,Combinatorics,Finite field,Disjoint sets,Polynomial,Factorization,True quantified Boolean formula,Multilinear map,Boolean expression,Mathematics | Journal |
Volume | Issue | ISSN |
41 | 3 | 1608-3261 |
Citations | PageRank | References |
3 | 0.45 | 7 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Pavel G. Emelyanov | 1 | 12 | 2.48 |
| Denis Ponomaryov | 2 | 29 | 7.43 |