State complexity characterizations of parameterized degree-bounded graph connectivity, sub-linear space computation, and the linear space hypothesis

DOI10.1007/978-3-319-94631-3_20zbMATH Open1435.68118arXiv1811.06336OpenAlexW2850503404MaRDI QIDQ5896095FDOQ5896095

Authors: Tomoyuki Yamakami 

Publication date: 30 June 2020

Published in: Theoretical Computer Science, Descriptional Complexity of Formal Systems (Search for Journal in Brave)

Abstract: 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$eq$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.

Full work available at URL: https://arxiv.org/abs/1811.06336

Recommendations

• State complexity characterizations of parameterized degree-bounded graph connectivity, sub-linear space computation, and the linear space hypothesis
• Parameterized graph connectivity and polynomial-time sub-linear-space short reductions (preliminary report)
• scientific article; zbMATH DE number 7204396
• Relating sublinear space computability among graph connectivity and related problems
• Two-Way Automata Characterizations of L/poly versus NL

zbMATH Keywords

state complexityalternating finite automatadirected graph connectivity problemlinear space hypothesisparameterized decision problemspolynomial-size advicesub-linear-space computability

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Directed graphs (digraphs), tournaments (05C20) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Connectivity (05C40) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Parameterized complexity, tractability and kernelization (68Q27)

Cites Work

• Alternation
• Turing machines that take advice
• Size Complexity of Two-Way Finite Automata
• Nondeterminism and the size of two way finite automata
• Title not available (Why is that?)
• Title not available (Why is that?)
• Two-way automata making choices only at the endmarkers
• Two-way unary automata versus logarithmic space
• Two-way automata versus logarithmic space
• Title not available (Why is that?)
• Title not available (Why is that?)
• A Sublinear Space, Polynomial Time Algorithm for Directed s-t Connectivity
• Parameterized graph connectivity and polynomial-time sub-linear-space short reductions (preliminary report)
• Two-way automata characterizations of L/poly versus NL
• Simultaneous Time-Space Upper Bounds for Red-Blue Path Problem in Planar DAGs

Cited In (7)

• Nonuniform families of polynomial-size quantum finite automata and quantum logarithmic-space computation with polynomial-size advice
• Unambiguity and fewness for nonuniform families of polynomial-size nondeterministic finite automata
• The 2CNF Boolean formula satisfiability problem and the linear space hypothesis
• How does adiabatic quantum computation fit into quantum automata theory?
• Unambiguous and co-nondeterministic computations of finite automata and pushdown automata families and the effects of multiple counters
• Elementary quantum recursion schemes that capture quantum polylogarithmic-time computability of quantum functions
• Power of counting by nonuniform families of polynomial-size finite automata

This page was built for publication: State complexity characterizations of parameterized degree-bounded graph connectivity, sub-linear space computation, and the linear space hypothesis

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5896095)