The degree structure of 1-L reductions

DOI10.1007/3-540-55808-X_13zbMath1496.03165OpenAlexW1855910751MaRDI QIDQ5096826

Hans-Jörg Burtschick, Albrecht Hoene

Publication date: 18 August 2022

Published in: Mathematical Foundations of Computer Science 1992 (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/3-540-55808-x_13

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Other degrees and reducibilities in computability and recursion theory (03D30)

Related Items (3)

DSPACE(\(n\)) \(\overset {?} =\) NSPACE(\(n\)): A degree theoretic characterization ⋮ The degree structure of 1-L reductions ⋮ Investigations Concerning the Structure of Complete Sets

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Some remarks on witness functions for nonpolynomial and noncomplete sets in NP
• On one-way functions and polynomial-time isomorphisms
• Isomorphisms and 1-L reductions
• Languages Simultaneously Complete for One-Way and Two-Way Log-Tape Automata
• Complete Problems and Strong Polynomial Reducibilities
• On Isomorphisms and Density of $NP$ and Other Complete Sets
• The isomorphism conjecture fails relative to a random oracle
• The degree structure of 1-L reductions

This page was built for publication: The degree structure of 1-L reductions