TR12-122 Authors: Giorgio Ausiello, Francesco Cristiano, Luigi Laura

Publication: 28th September 2012 15:52

Downloads: 3893

Keywords:

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).