Decompositions of nondeterministic reductions (Q1108263): Difference between revisions
From MaRDI portal
Set profile property. |
Set OpenAlex properties. |
||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1016/0304-3975(88)90025-4 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2062265191 / rank | |||
Normal rank |
Revision as of 19:29, 19 March 2024
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