SUCCINCT REPRESENTATIONS OF GRAPHS
SUCCINCT REPRESENTATIONS OF GRAPHS
复制标题
DOI：
10.1016/s0019-9958(83)80004-7
复制
发表时间：
1983-01-01
影响因子：
--
通讯作者：
WIGDERSON, A
中科院分区：
文献类型：
--
作者：
GALPERIN, H;WIGDERSON, A
对于一个固定的图性质Q，问题的复杂性：给定一个图G，G是否具有性质Q？通常作为一个函数来研究，|V|，G中的顶点数，假设输入大小是多项式，|V|.在本文中，这些问题的复杂性时，输入图是由一个简洁的表示。简洁的表示意味着输入大小是polylog in| V|.它表明，图形的问题，这是接近这种方式变得棘手。事实上，没有“非平凡”的问题可以找到，可以解决在多项式时间。主要结果是表征一个大类的图形属性，其各自的“简洁的问题”是NP-难的。试图在P-时间层次中定位这些问题表明，多项式等价问题的简洁版本可能不是多项式等价的。
For a fixed graph propertyQ, the complexity of the problem: Given a graphG, doesGhave propertyQ? is usually investigated as a function of |V|, the number of vertices inG, with the assumption that the input size is polynomial in |V|. In this paper the complexity of these problems is investigated when the input graph is given by a succinct representation. By a succinct representation it is meant that the input size is polylog in |V|. It is shown that graph problems which are approached this way become intractable. Actually, no “nontrivial” problem could be found which can be solved in polynomial time. The main result is characterizing a large class of graph properties for which the respective “succinct problem” is NP-hard. Trying to locate these problems within the P-Time hierarchy shows that the succinct versions of polynomially equivalent problems may not be polynomially equivalent.