On Reducibility to Complex or Sparse Sets
From MaRDI portal
Publication:4069780
DOI10.1145/321892.321895zbMath0311.68037OpenAlexW2095229434MaRDI QIDQ4069780
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)
Related Items
Nonlevelable sets and immune sets in the accepting density hierarchy inNP, On solving hard problems by polynomial-size circuits, Almost every set in exponential time is P-bi-immune, A classification of complexity core lattices, The structure of generalized complexity cores, Unnamed Item, Classifying the computational complexity of problems, OnP-subset structures, On the structure of sets in NP and other complexity classes, On the complexity of test case generation for NP-hard problems, On polynomial-time Turing and many-one completeness in PSPACE, Complexity-class-encoding sets, Exponential-time and subexponential-time sets, On inefficient special cases of NP-complete problems, On hard instances, Resource bounded immunity and simplicity, Bi-immune sets for complexity classes
