|
| | | | |
| | | |
| Stat |
Members: 3645
Articles: 2'504'928
Articles rated: 2609
25 April 2024 |
|
| | | | |
|
Article forum
| |
|
|
State Complexity Characterizations of Parameterized Degree-Bounded Graph Connectivity, Sub-Linear Space Computation, and the Linear Space Hypothesis | | Tomoyuki Yamakami
; | | Date: |
15 Nov 2018 | | 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 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 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 non-uniform version of the linear space hypothesis in
terms of the state complexity of transformation. | | Source: | arXiv, 1811.6336 | | Services: | Forum | Review | PDF | Favorites | |
|
|
No message found in this article forum.
You have a question or message about this article?
Ask the community and write a message in the forum.
If you want to rate this article, please use the review section..
To add a message in the forum, you need to login or register first. (free): registration page
|
| |
|
|
|
|
News, job offers and information for researchers and scientists:
| |
REGISTER