On Reducibility to Complex or Sparse Sets

DOI10.1145/321892.321895zbMath0311.68037OpenAlexW2095229434MaRDI QIDQ4069780

Nancy A. Lynch

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

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Recursively (computably) enumerable sets and degrees (03D25)

Related Items (17)

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

This page was built for publication: On Reducibility to Complex or Sparse Sets