Complexity-class-encoding sets

DOI10.1016/S0022-0000(76)80054-2zbMATH Open0355.68039MaRDI QIDQ1237360FDOQ1237360

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

• Title not available (Why is that?)
• Title not available (Why is that?)
• The complexity of theorem-proving procedures
• Classes of computable functions defined by bounds on computation
• A Machine-Independent Theory of the Complexity of Recursive Functions
• Title not available (Why is that?)
• A comparison of polynomial time reducibilities
• Title not available (Why is that?)
• An Overview of the Theory of Computational Complexity
• On Reducibility to Complex or Sparse Sets
• On Sets Cook-Reducible to Sparse Sets

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)