State complexity characterizations of parameterized degree-bounded graph connectivity, sub-linear space computation, and the linear space hypothesis
State complexity characterizations of parameterized degree-bounded graph connectivity, sub-linear space computation, and the linear space hypothesis
复制标题
参数化有界图连通性、次线性空间计算和线性空间假设的状态复杂性表征
DOI：
10.1016/j.tcs.2019.09.006
复制
发表时间：
2019
影响因子：
1.1
通讯作者：
Tomoyuki Yamakami
中科院分区：
文献类型：
--
作者：
Henning Fernau;Petra Wolf;Tomoyuki Yamakami;Tomoyuki Yamakami
线性空间假设是一个实用的工作假设，它最初陈述了由布尔变量数量参数化的受限 2CNF 布尔公式可满足性问题的不可解性。根据这个假设，自然可以得出，由给定图中的顶点数量参数化的 3 度有向图连通性问题 (3DSTCON) 不能属于 PsubLIN，它由可由多项式时间、亚线性空间确定性图灵机计算的所有参数化决策问题组成。该假设立即暗示了 L≠NL，并且它被用作获得各种 NL 搜索和 NL 优化问题的计算复杂性的新下界的坚实基础。变换的状态复杂度是指将一种类型的有限自动机转换为另一种类型的成本，该成本以转换后的自动机相对于原始自动机的内部状态数量的增加来衡量。我们将线性空间假设与将受限的 2 路非确定性有限自动机转换为计算等效的具有狭窄计算图的 2 路交替有限自动机的状态复杂性相关联。为此，我们提出了 3DSTCON 和 PsubLIN 的状态复杂性特征。我们进一步根据变换的状态复杂度来表征线性空间假设的非均匀版本。
The linear space hypothesis is a practical working hypothesis, which originally states the insolvability of a restricted 2CNF Boolean formula satisfiability problem parameterized by the number of Boolean variables. From this hypothesis, it naturally follows that the degree-3 directed graph connectivity problem (3DSTCON) parameterized by the number of vertices in a given graph cannot belong to PsubLIN, composed of all parameterized decision problems computable by polynomial-time, sub-linear-space deterministic Turing machines. This hypothesis immediately implies L≠NL and it was used as a solid foundation to obtain new lower bounds on the computational complexity of various NL search and NL optimization problems. The state complexity of transformation refers to the cost of converting one type of finite automata to another type, where the cost is measured in terms of the increase of the number of inner states of the converted automata from that of the original automata. We relate the linear space hypothesis to the state complexity of transforming restricted 2-way nondeterministic finite automata to computationally equivalent 2-way alternating finite automata having narrow computation graphs. For this purpose, we present state complexity characterizations of 3DSTCON and PsubLIN. We further characterize a nonuniform version of the linear space hypothesis in terms of the state complexity of transformation.