Publication:3312209
From MaRDI portal
zbMath0531.03020MaRDI QIDQ3312209
Publication date: 1983
reducibility; NP-completeness; diagonalization; provability; recursive languages; complexity classes; recursive presentations; countable posets; polynomial- isomorphism
68Q25: Analysis of algorithms and problem complexity
68Q45: Formal languages and automata
03D15: Complexity of computation (including implicit computational complexity)
03D30: Other degrees and reducibilities in computability and recursion theory
03D10: Turing machines and related notions
03D60: Computability and recursion theory on ordinals, admissible sets, etc.
Related Items
Canonical disjoint NP-pairs of propositional proof systems, 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.