Complexity-class-encoding sets

DOI10.1016/S0022-0000(76)80054-2zbMath0355.68039MaRDI QIDQ1237360

Nancy A. Lynch

Publication date: 1976

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Recursive functions and relations, subrecursive hierarchies (03D20) Recursively (computably) enumerable sets and degrees (03D25) Turing machines and related notions (03D10)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A comparison of polynomial time reducibilities
• On Reducibility to Complex or Sparse Sets
• On Sets Cook-Reducible to Sparse Sets
• Classes of computable functions defined by bounds on computation
• A Machine-Independent Theory of the Complexity of Recursive Functions
• An Overview of the Theory of Computational Complexity
• The complexity of theorem-proving procedures

This page was built for publication: Complexity-class-encoding sets