On the relative complexity of hard problems for complexity classes without complete problems
From MaRDI portal
Publication:1112017
DOI10.1016/0304-3975(89)90066-2zbMath0659.03022OpenAlexW2065826812WikidataQ128122778 ScholiaQ128122778MaRDI QIDQ1112017
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
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
