Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > AUTHORS > FRANCESCO CRISTIANO:
All reports by Author Francesco Cristiano:

TR12-122 | 17th September 2012
Giorgio Ausiello, Francesco Cristiano, Luigi Laura

Syntactic Isomorphism of CNF Boolean Formulas is Graph Isomorphism Complete

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




ISSN 1433-8092 | Imprint