On Reducibility to Complex or Sparse Sets
From MaRDI portal
Publication:4069780
DOI10.1145/321892.321895zbMATH Open0311.68037OpenAlexW2095229434MaRDI QIDQ4069780FDOQ4069780
Publication date: 1975
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/321892.321895
Analysis of algorithms and problem complexity (68Q25) Recursively (computably) enumerable sets and degrees (03D25)
Cited In (17)
- Complexity-class-encoding sets
- On polynomial-time Turing and many-one completeness in PSPACE
- On solving hard problems by polynomial-size circuits
- A classification of complexity core lattices
- The structure of generalized complexity cores
- Resource bounded immunity and simplicity
- Title not available (Why is that?)
- Bi-immune sets for complexity classes
- Exponential-time and subexponential-time sets
- Almost every set in exponential time is P-bi-immune
- On the complexity of test case generation for NP-hard problems
- Nonlevelable sets and immune sets in the accepting density hierarchy inNP
- Classifying the computational complexity of problems
- OnP-subset structures
- On inefficient special cases of NP-complete problems
- On the structure of sets in NP and other complexity classes
- On hard instances
This page was built for publication: On Reducibility to Complex or Sparse Sets
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4069780)
