On Reducibility to Complex or Sparse Sets

DOI10.1145/321892.321895MaRDI QIDQ4069780zbMATH OpenOpenAlexFDO

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

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

Cited in

(17)

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

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)