Decompositions of nondeterministic reductions

DOI10.1016/0304-3975(88)90025-4zbMath0654.03025OpenAlexW2062265191MaRDI QIDQ1108263

Klaus-Joern Lange

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

zbMATH Keywords

determinismpolynomial timeTuring reducibilitynondeterminismlogarithmic spacerelativizationsmany-one reducibility

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Complexity of computation (including implicit computational complexity) (03D15) Hierarchies of computability and definability (03D55)

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

This page was built for publication: Decompositions of nondeterministic reductions