scientific article; zbMATH DE number 3841832

MaRDI QIDQ3312209zbMATH OpenFDO

Authors Kenneth W. Regan

Publication date 1983

zbMATH Keywords

complexity classescountable posetsdiagonalizationNP-completenesspolynomial- isomorphismprovabilityrecursive languagesrecursive presentationsreducibility

Mathematics Subject Classification ID

Turing machines and related notions (03D10) Complexity of computation (including implicit computational complexity) (03D15) Other degrees and reducibilities in computability and recursion theory (03D30) Computability and recursion theory on ordinals, admissible sets, etc. (03D60) Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45)

Recommendations

• scientific article; zbMATH DE number 4121422
• scientific article; zbMATH DE number 3877163
• scientific article; zbMATH DE number 4012593
• The p-T-degrees of the recursive sets: Lattice embeddings, extensions of embeddings and the two-quantifier theory
• scientific article; zbMATH DE number 3869313

Cited in

(11)

• The recursion-theoretic structure of complexity classes
• Isomorphisms and 1-L reductions
• Simplicity, immunity, relativizations and nondeterminism
• Diagonalization, uniformity, and fixed-point theorems
• Gap-languages and log-time complexity classes
• Uniformly hard languages.
• scientific article; zbMATH DE number 4012593 (Why is no real title available?)
• scientific article; zbMATH DE number 3596249 (Why is no real title available?)
• scientific article; zbMATH DE number 512990 (Why is no real title available?)
• scientific article; zbMATH DE number 4121422 (Why is no real title available?)
• Canonical disjoint NP-pairs of propositional proof systems

This page was built for publication:

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