Decompositions of nondeterministic reductions

DOI10.1016/0304-3975(88)90025-4MaRDI QIDQ1108263zbMATH OpenOpenAlexFDO

Authors Klaus-Jörn 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

determinismlogarithmic spacenondeterminismpolynomial timerelativizationsmany-one reducibilityTuring reducibility

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 3960995
• scientific article; zbMATH DE number 3904572
• Characterizations of reduction classes modulo oracle conditions
• The relative power of logspace and polynomial time reductions
• On Nondeterminism, Enumeration Reducibility and Polynomial Bounds

Cites work

• scientific article; zbMATH DE number 3904572 (Why is no real title available?)
• scientific article; zbMATH DE number 3560737 (Why is no real title available?)
• A comparison of polynomial time reducibilities
• A note on relativized log space
• Alternation
• Complete sets and the polynomial-time hierarchy
• Log Space Recognition and Translation of Parenthesis Languages
• On uniform circuit complexity
• Relativization of questions about log space computability
• Separation with the Ruzzo, Simon, and Tompa relativization implies DSPACE(log n)\(\neq NSPACE(\log \,n)\)
• Space-bounded hierarchies and probabilistic computations
• Strong nondeterministic polynomial-time reducibilities
• The complexity of facets (and some facets of complexity)
• The complexity of theorem-proving procedures
• Tree-size bounded alternation

Cited in

(7)

• On adaptive DLOGTIME and POLYLOGTIME reductions
• scientific article; zbMATH DE number 3960995 (Why is no real title available?)
• scientific article; zbMATH DE number 4043254 (Why is no real title available?)
• scientific article; zbMATH DE number 3904572 (Why is no real title available?)
• Nonuniform reductions and NP-completeness
• scientific article; zbMATH DE number 4037175 (Why is no real title available?)
• Decompositions and reductions of snarks

This page was built for publication: Decompositions of nondeterministic reductions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1108263)