State Complexity Characterizations of Parameterized Degree-Bounded Graph Connectivity, Sub-Linear Space Computation, and the Linear Space Hypothesis (Preliminary Report)

• Item type: SIG Technical Reports(1)
• 公開日: 2018-05-18
• タイトル: State Complexity Characterizations of Parameterized Degree-Bounded Graph Connectivity, Sub-Linear Space Computation, and the Linear Space Hypothesis (Preliminary Report)
• タイトル / 言語: en
• タイトル: State Complexity Characterizations of Parameterized Degree-Bounded Graph Connectivity, Sub-Linear Space Computation, and the Linear Space Hypothesis (Preliminary Report)
• 言語: eng
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: Department of Information Science, University of Fukui
• 著者所属(英): en
• 著者所属(英): Department of Information Science, University of Fukui
• 著者名: Tomoyuki, Yamakami
• 著者名(英): Tomoyuki, Yamakami
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: The linear space hypothesis is a practical working hypothesis, which originally states the insolvability of a restricted 2CNF Boolean formula satisfiability problem (2SAT3) with respect to the number of Boolean variables. From this hypothesis, it follows that the degree-3 directed graph connectivity problem (3DSTCON) parameterized by the number of vertices in a given graph cannot belong to PsubLIN (characterized 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 of 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 the original number. We relate the linear space hypothesis to the state complexity of transforming restricted 2-way nondeterministic finite automata to equivalent 2-way alternating finite automata having narrow computation trees. For this purpose, we present state complexity characterizations of 3DSTCON and PsubLIN. We further characterize a non-uniform version of the linear space hypothesis in terms of state complexity of transformation.
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: The linear space hypothesis is a practical working hypothesis, which originally states the insolvability of a restricted 2CNF Boolean formula satisfiability problem (2SAT3) with respect to the number of Boolean variables. From this hypothesis, it follows that the degree-3 directed graph connectivity problem (3DSTCON) parameterized by the number of vertices in a given graph cannot belong to PsubLIN (characterized 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 of 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 the original number. We relate the linear space hypothesis to the state complexity of transforming restricted 2-way nondeterministic finite automata to equivalent 2-way alternating finite automata having narrow computation trees. For this purpose, we present state complexity characterizations of 3DSTCON and PsubLIN. We further characterize a non-uniform version of the linear space hypothesis in terms of state complexity of transformation.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 研究報告アルゴリズム（AL）; 巻 2018-AL-168, 号 1, p. 1-7, 発行日 2018-05-18
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 2188-8566
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会