CNF and DNF succinct graph encodings
CNF and DNF succinct graph encodings
复制标题
CNF 和 DNF 简洁图编码
DOI：
10.1016/j.ic.2016.06.009
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
Jacobo Torán
中科院分区：
文献类型：
--
作者：
Bireswar Das;Patrick Scharpfenecker;Jacobo Torán
众所周知，计算问题的简洁编码-使用电路或公式来编码大型实例-通常会导致复杂度与原始复杂度相比呈指数级增长。我们介绍了一种新的编码方法，基于CNF或DNF公式。我们表明，-与其他现有的简洁的模型-有问题的复杂性不增加时，在新的形式编码的例子，或增加到一个中间的复杂性类不太强大的指数blowup.We还研究了复杂性的简洁版本的图同构问题。我们表明，所有的版本是很难的PSPACE。虽然这些问题的确切复杂性仍然是未知的，我们表明，在大多数现有的简洁模型的不同版本的问题是等效的。我们还给出了一个算法的DNF编码版本的GI，其运行时间主要取决于在简洁的表示的术语的数量。
It is well-known that succinct encodings of computational problems – using circuits or formulas to encode large instances – generally result in an exponential complexity blow-up compared to their original complexity.We introduce a new way to encode 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 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.
登录
查看更多内容
关于图的简洁表示的注解
DOI：
10.1016/s0019-9958(86)80009-2
发表时间：
1986
期刊：
Inf. Control.
影响因子：
--
作者：
C. Papadimitriou;M. Yannakakis
通讯作者：
M. Yannakakis
影响因子：
0.5
作者：
J. Torán
通讯作者：
J. Torán
连接性要求对最大子图问题复杂性的影响
DOI：
--
发表时间：
1979
期刊：
JACM
影响因子：
--
作者：
M. Yannakakis
通讯作者：
M. Yannakakis
当地折扣
DOI：
--
发表时间：
2013
期刊：
International Colloquium on Automata, Languages and Programming
影响因子：
--
作者：
Hamidreza Jahanjou;Eric Miles;Emanuele Viola
通讯作者：
Emanuele Viola
影响因子：
1.4
作者：
Eric Allender;D. Holden;Valentine Kabanets
通讯作者：
Eric Allender;D. Holden;Valentine Kabanets