CNF and DNF succinct graph encodings

We also study the complexity of the succinct versions of the Graph Isomorphism problem. We show that all the versions are hard for PSPACE. Although the exact complexity of these problems is still unknown, we show that under most existing succinct models the different versions of the problem are equivalent. We also give an algorithm for the DNF encoded version of GI whose running time depends mainly on the number of terms in the succinct representation.