Succinct Encodings of Graph Isomorphism
Succinct Encodings of Graph Isomorphism
复制标题
图同构的简洁编码
DOI：
10.1007/978-3-319-04921-2_23
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
J. Torán
中科院分区：
文献类型：
--
作者：
Bireswar Das;Patrick Scharpfenecker;J. Torán
众所周知，用电路或公式编码的问题与其原始复杂度相比通常会获得指数复杂度爆炸。
我们介绍了一种新的方法编码图的问题，CNF或DNF公式的基础上。我们表明，与其他现有的简洁的模型，有一些例子的问题，其复杂性不会增加时，编码在新的形式，或增加到一个中间的复杂性类不太强大的指数爆炸。
我们还研究了图同构问题的简洁版本的复杂性。我们表明，所有的版本是很难的PSPACE。虽然这些问题的确切复杂性是未知的，我们表明，在大多数现有的简洁模型的不同版本的问题是等效的。我们还给出了一个算法的DNF编码版本的GI的运行时间只取决于简洁的表示的大小。
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 CNF or 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 PSPACE. Although the exact complexity of these problems is not known, 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 only on the size of the succinct representation.