On Reducibility to Complex or Sparse Sets

DOI10.1145/321892.321895MaRDI QIDQ4069780zbMATHOpenAlexFDO

Authors Nancy 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)

Cited in

(17)

• Almost every set in exponential time is P-bi-immune
• scientific article; zbMATH DE number 3619885 (Why is no real title available?)
• On polynomial-time Turing and many-one completeness in PSPACE
• On the complexity of test case generation for NP-hard problems
• On hard instances
• Nonlevelable sets and immune sets in the accepting density hierarchy inNP
• Classifying the computational complexity of problems
• Resource bounded immunity and simplicity
• On solving hard problems by polynomial-size circuits
• On inefficient special cases of NP-complete problems
• A classification of complexity core lattices
• Bi-immune sets for complexity classes
• The structure of generalized complexity cores
• On the structure of sets in NP and other complexity classes
• Exponential-time and subexponential-time sets
• Complexity-class-encoding sets
• OnP-subset structures

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)