scientific article

zbMath0531.03020MaRDI QIDQ3312209

Kenneth W. Regan

Publication date: 1983

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

zbMATH Keywords

reducibilityNP-completenessdiagonalizationprovabilityrecursive languagescomplexity classesrecursive presentationscountable posetspolynomial- isomorphism

Mathematics Subject Classification ID

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

Related Items

Uniformly hard languages., Isomorphisms and 1-L reductions, Simplicity, immunity, relativizations and nondeterminism, Canonical disjoint NP-pairs of propositional proof systems, Gap-languages and log-time complexity classes, Diagonalization, uniformity, and fixed-point theorems, The recursion-theoretic structure of complexity classes