Complexity-class-encoding sets

DOI10.1016/S0022-0000(76)80054-2MaRDI QIDQ1237360zbMATHFDO

Authors Nancy Lynch

Publication date 1976

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

Mathematics Subject Classification ID

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

Cites work

• scientific article; zbMATH DE number 3501006 (Why is no real title available?)
• scientific article; zbMATH DE number 3571502 (Why is no real title available?)
• scientific article; zbMATH DE number 3291134 (Why is no real title available?)
• scientific article; zbMATH DE number 3311755 (Why is no real title available?)
• A Machine-Independent Theory of the Complexity of Recursive Functions
• A comparison of polynomial time reducibilities
• An Overview of the Theory of Computational Complexity
• Classes of computable functions defined by bounds on computation
• On Reducibility to Complex or Sparse Sets
• On Sets Cook-Reducible to Sparse Sets
• The complexity of theorem-proving procedures

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1237360)