Decompositions of nondeterministic reductions (Q1108263)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: Decompositions of nondeterministic reductions |
scientific article; zbMATH DE number 4066858
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | Decompositions of nondeterministic reductions |
scientific article; zbMATH DE number 4066858 |
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
0.8369327187538147
0 references
0.7766888737678528
0 references
0.7722665071487427
0 references
