Decompositions of nondeterministic reductions (Q1108263)
From MaRDI portal
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Decompositions of nondeterministic reductions |
scientific article |
Statements
Decompositions of nondeterministic reductions (English)
0 references
1988
0 references
Turing reducibility, conjunctive Turing reducibility, and many-one reducibility are related and compared with respect to determinism vs. nondeterminism and polynomial time vs. logarithmic space. By relativizing some equations relating polynomial time and logarithmic space classes via formal language operations the author obtains a characterization of the nondeterministic reductions with a polynomial time or logarithmic space bound in terms of nonerasing homomorphism and Kleene's star.
0 references
relativizations
0 references
Turing reducibility
0 references
many-one reducibility
0 references
determinism
0 references
nondeterminism
0 references
polynomial time
0 references
logarithmic space
0 references
