ECCC-Report TR12-122https://eccc.weizmann.ac.il/report/2012/122Comments and Revisions published for TR12-122en-usFri, 28 Sep 2012 15:52:44 +0200
Paper TR12-122
| Syntactic Isomorphism of CNF Boolean Formulas is Graph Isomorphism Complete |
Giorgio Ausiello,
Francesco Cristiano,
Luigi Laura
https://eccc.weizmann.ac.il/report/2012/122We 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).Fri, 28 Sep 2012 15:52:44 +0200https://eccc.weizmann.ac.il/report/2012/122