|
| | | | |
| | | |
| Stat |
Members: 3645
Articles: 2'501'711
Articles rated: 2609
20 April 2024 |
|
| | | | |
|
Article overview
| |
|
|
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 review found.
Did you like this article?
Note: answers to reviews or questions about the article must be posted in the forum section.
Authors are not allowed to review their own article. They can use the forum section.
|
| |
|
|
|
|
News, job offers and information for researchers and scientists:
| |
REGISTER