Name
Abstract | ||
|---|---|---|
Disjoint AND-decomposition of a boolean formula means its representation as a conjunction of two (or several) formulas having disjoint sets of variables. We show that deciding AND-decomposability is intractable in general for boolean formulas given in CNF or DNF and prove tractability of computing AND-decompositions of boolean formulas given in positive DNF, Full DNF, and ANF. The results follow 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 |
|---|---|---|
2014 | 10.1007/978-3-662-46823-4_8 | PERSPECTIVES OF SYSTEM INFORMATICS, PSI 2014 |
Field | DocType | Volume |
Combinatorics,Finite field,Disjoint sets,Polynomial,Multilinear polynomial,Partial derivative,Factorization,True quantified Boolean formula,Multilinear map,Mathematics | Conference | 8974 |
ISSN | Citations | PageRank |
0302-9743 | 2 | 0.44 |
References | Authors | |
8 | 2 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Pavel G. Emelyanov | 1 | 12 | 2.48 |
| Denis Ponomaryov | 2 | 29 | 7.43 |