All reports by Author Giorgio Ausiello:

__
TR12-122
| 17th September 2012
__

Giorgio Ausiello, Francesco Cristiano, Luigi Laura#### Syntactic Isomorphism of CNF Boolean Formulas is Graph Isomorphism Complete

Giorgio Ausiello, Francesco Cristiano, Luigi Laura

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