论文标题
参数化 - NL组合问题的完整性通过短对数空间的降低和线性空间假设的直接后果
Parameterized-NL Completeness of Combinatorial Problems by Short Logarithmic-Space Reductions and Immediate Consequences of the Linear Space Hypothesis
论文作者
论文摘要
在限制内存限制的计算设备上处理庞大的数据集方面，有空间的可计算性的概念变得非常重要。为了补充现有的NL核算问题的简短列表，其实例大小由日志空间大小参数决定，我们提出了直接从三个典型NP NP完整问题的自然参数中获得的新添加剂，即顶点覆盖问题 - 顶点覆盖率问题，由3个组的问题确切覆盖，由3群问题以及3维匹配的匹配问题。由于对其实例施加了适当的限制，事实证明，通过适当大小参数参数参数的拟议决策问题在计算复杂性方面与参数化的$ 3 $ 3 $结合的2cnf Boolean公式可满足性问题或参数化度 - $ 3 $ 3 $ S $ S $ -S $ T $ CONCEMATITY CONCEMATION。在线性空间假设的假设下，如果记忆使用限于亚线性空间，则不能在多项式时间内解决任何提出的问题。
The concept of space-bounded computability has become significantly important in handling vast data sets on memory-limited computing devices. To replenish the existing short list of NL-complete problems whose instance sizes are dictated by log-space size parameters, we propose new additions obtained directly from natural parameterizations of three typical NP-complete problems -- the vertex cover problem, the exact cover by 3-sets problem, and the 3-dimensional matching problem. With appropriate restrictions imposed on their instances, the proposed decision problems parameterized by appropriate size parameters are proven to be equivalent in computational complexity to either the parameterized $3$-bounded 2CNF Boolean formula satisfiability problem or the parameterized degree-$3$ directed $s$-$t$ connectivity problem by ``short'' logarithmic-space reductions. Under the assumption of the linear space hypothesis, furthermore, none of the proposed problems can be solved in polynomial time if the memory usage is limited to sub-linear space.
