Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR15-100 | 16th June 2015 10:00

Succinct Encodings of Graph Isomorphism


Authors: Bireswar Das, Patrick Scharpfenecker, Jacobo Toran
Publication: 19th June 2015 23:10
Downloads: 856


It is well known that problems encoded with circuits or formulas generally gain an exponential complexity blow-up compared to their original complexity.

We introduce a new way for encoding graph problems, based on $\textrm{CNF}$ or $\textrm{DNF}$ formulas. We show that contrary to the other existing succinct models, there are examples of problems whose complexity does not increase when encoded in the new form, or increases to an intermediate complexity class less powerful than the exponential blow up.

We also study the complexity of the succinct versions of the Graph Isomorphism problem. We show that all the versions are hard for $\textrm{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 $\textrm{DNF}$ encoded version of $\textrm{GI}$ whose running time depends only on the size of the succinct representation.

ISSN 1433-8092 | Imprint