|
| | | | |
| | | |
| Stat |
Members: 3645
Articles: 2'500'096
Articles rated: 2609
18 April 2024 |
|
| | | | |
|
Article forum
| |
|
|
Supportive Oracles for Parameterized Polynomial-Time Sub-Linear-Space Computations in Relation to L, NL, and P | | Tomoyuki Yamakami
; | | Date: |
17 Jan 2019 | | Abstract: | We focus our attention onto polynomial-time sub-linear-space computation for
decision problems, which are parameterized by size parameters $m(x)$, where the
informal term "sub linear" means a function of the form
$m(x)^{varepsilon}cdot polylog(|x|)$ on input instances $x$ for a certain
absolute constant $varepsilonin(0,1)$ and a certain polylogarithmic function
$polylog(n)$. The parameterized complexity class PsubLIN consists of all
parameterized decision problems solvable simultaneously in polynomial time
using sub-linear space. This complexity class is associated with the linear
space hypothesis. There is no known inclusion relationships between PsubLIN and
para-NL (nondeterministic log-space class), where the prefix "para-" indicates
the natural parameterization of a given complexity class. Toward circumstantial
evidences for the inclusions and separations of the associated complexity
classes, we seek their relativizations. However, the standard relativization of
Turing machines is known to violate the relationships of
L$subseteq$NL=co-NL$subseteq$DSPACE[O($log^2{n}$)]$cap$P. We instead
consider special oracles, called NL-supportive oracles, which guarantee these
relationships in the corresponding relativized worlds. This paper vigorously
constructs such NL-supportive oracles that generate relativized worlds where,
for example, para-L$
eq$para-NL$
subseteq$PsubLIN and
para-L$
eq$para-NL$subseteq$PsubLIN. | | Source: | arXiv, 1901.5854 | | 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