Parameterized graph connectivity and polynomial-time sub-linear-space short reductions (preliminary report)
Parameterized graph connectivity and polynomial-time sub-linear-space short reductions (preliminary report)
复制标题
参数化图连通性和多项式时间子线性空间短约简（初步报告）
DOI：
10.1007/978-3-319-67089-8_13
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
Tomoyuki Yamakami
中科院分区：
文献类型：
--
作者：
Tomoyuki Yamakami;Tomoyuki Yamakami;Tomoyuki Yamakami;Tomoyuki Yamakami;Tomoyuki Yamakami
我们专注于有向连通性问题（DSTCON）的可解性/不可解性，该问题由合适的尺寸参数sm（x）参数化，在多带确定性图灵机上，通过同时消耗多项式时间和次线性空间来处理实例xto DSTCON，其中非正式术语“次线性”指的是针对某个绝对常数和某个多对数函数的形式子实例x的函数。作为自然尺寸参数，我们取x中的图的顶点数和边数。利用次线性空间在多项式时间内可同时求解的参数化问题形成了一个复杂性类，并且不知道参数化问题是否属于。对于这个开放的问题，我们希望调查的相对复杂性和它的自然变种，并将它们分类根据一个限制形式的多一个和图灵减少，被称为“短减少”，保持多项式时间的子线性空间的复杂性。作为的变体，我们考虑广度优先搜索问题，最小路径问题，和拓扑排序问题。它们的某些限制形式属于。我们还考虑“次线性”的更强版本，称为“次线性”。此外，我们还提到了与一个实际工作假设的关系，称为线性空间假设。
We are focused on the solvability/insolvability of the directeds-tconnectivity problem (DSTCON) parameterized by suitable size parametersm(x) on multi-tape deterministic Turing machines working on instancesxto DSTCON by consuming simultaneously polynomial time and sub-linear space, where the informal term “sub-linear” refers to a function of the formon instancesxfor a certain absolute constantand a certain polylogarithmic function. As natural size parameters, we take the numbersof vertices and of edgesof a graph cited inx. Parameterized problems solvable simultaneously in polynomial time using sub-linear space form a complexity classand it is unknown whetherparameterized bybelongs to. Toward this open question, we wish to investigate the relative complexity ofand its natural variants and classify them according to a restricted form of many-one and Turing reductions, known as “short reductions,” which preserve the polynomial-time sub-linear-space complexity. As variants of, we consider the breadth-first search problem, the minimal path problem, and the topological sorting problem. Certain restricted forms of them fall into. We also consider a stronger version of “sub-linear,” called “hypo-linear.” Additionally, we refer to a relationship to a practical working hypothesis known as the linear space hypothesis.