Decompositions of nondeterministic reductions
From MaRDI portal
Publication:1108263
DOI10.1016/0304-3975(88)90025-4zbMath0654.03025MaRDI QIDQ1108263
Publication date: 1988
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0304-3975(88)90025-4
determinism; polynomial time; Turing reducibility; nondeterminism; logarithmic space; relativizations; many-one reducibility
68Q25: Analysis of algorithms and problem complexity
03D15: Complexity of computation (including implicit computational complexity)
03D55: Hierarchies of computability and definability
Cites Work
- Unnamed Item
- Unnamed Item
- Strong nondeterministic polynomial-time reducibilities
- The complexity of facets (and some facets of complexity)
- Space-bounded hierarchies and probabilistic computations
- Separation with the Ruzzo, Simon, and Tompa relativization implies DSPACE(log n)\(\neq NSPACE(\log \,n)\)
- Tree-size bounded alternation
- On uniform circuit complexity
- A comparison of polynomial time reducibilities
- Complete sets and the polynomial-time hierarchy
- A note on relativized log space
- Alternation
- Relativization of questions about log space computability
- Log Space Recognition and Translation of Parenthesis Languages
- The complexity of theorem-proving procedures