Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Paper:

TR12-122 | 17th September 2012 14:48

#### Syntactic Isomorphism of CNF Boolean Formulas is Graph Isomorphism Complete

TR12-122
Authors: Giorgio Ausiello, Francesco Cristiano, Luigi Laura
Publication: 28th September 2012 15:52
Downloads: 2881
Keywords:

Abstract:

We investigate the complexity of the syntactic isomorphism problem of CNF Boolean Formulas (CSFI): given two CNF Boolean formulas $\varphi(a_{1},\ldots,a_{n})$ and $\varphi(b_{1},\ldots,b_{n})$ decide whether there exists a permutation of clauses, a permutation of literals and a bijection between their variables such that $\varphi(a_{1},\ldots,a_{n})$ and $\varphi(b_{1},\ldots,b_{n})$ become syntactically identical. We first show that the CSFI problem is polynomial time reducible to the graph isomorphism problem (GI) and then we show that GI is polynomial time reducible to a special case of the CSFI problem (MCSFI) that is CSFI-complete and also GI-complete, thus concluding that the syntactic isomorphism problem for CNF Boolean formulas is GI-complete. Finally we observe that the same results hold when considering DNF Boolean formulas (DSFI).

ISSN 1433-8092 | Imprint