On the relative complexity of hard problems for complexity classes without complete problems

DOI10.1016/0304-3975(89)90066-2zbMath0659.03022OpenAlexW2065826812WikidataQ128122778 ScholiaQ128122778MaRDI QIDQ1112017

Ambos-Spies, Klaus

Publication date: 1989

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(89)90066-2

zbMATH Keywords

recursive setshard problemscomplete problemssparse setcomplexity classpolynomial time reducibility

Mathematics Subject Classification ID

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

Related Items (5)

A characterization of the leaf language classes ⋮ Unnamed Item ⋮ Regular reals ⋮ h-monotonically computable real numbers ⋮ Hyper-polynomial hierarchies and the polynomial jump

Cites Work

• A note on complete problems for complexity classes
• A note on structure and looking back applied to the relative complexity of computable functions
• On the structure of sets in NP and other complexity classes
• A uniform approach to obtain diagonal sets in complexity classes
• Sparse complete sets for NP: solution of a conjecture of Berman and Hartmanis
• Relative complexity of checking and evaluating
• The polynomial-time hierarchy
• Complete sets and the polynomial-time hierarchy
• Computation times of NP sets of different densities
• Sublattices of the polynomial time degrees
• On the Structure of Polynomial Time Reducibility
• Computational Complexity of Probabilistic Turing Machines
• P-selective sets, tally languages, and the behavior of polynomial time reducibilities onNP
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: On the relative complexity of hard problems for complexity classes without complete problems