A note on structure and looking back applied to the relative complexity of computable functions

DOI10.1016/0022-0000(81)90021-0zbMath0474.68063OpenAlexW2032079969MaRDI QIDQ1158964

Michael Machtey, Paul Chew

Publication date: 1981

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

Full work available at URL: https://doi.org/10.1016/0022-0000(81)90021-0

zbMATH Keywords

complexity classessubrecursive degreesenumeration properties of classes of computable functionssubrecursive reducibilities

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Applications of computability and recursion theory (03D80) Other degrees and reducibilities in computability and recursion theory (03D30) Theory of numerations, effectively presented structures (03D45) Computability and recursion theory on ordinals, admissible sets, etc. (03D60)

Related Items

Uniformly hard languages., Some remarks on witness functions for nonpolynomial and noncomplete sets in NP, Minimal pairs and complete problems, A complexity theory for feasible closure properties, Generality's price: Inescapable deficiencies in machine-learned programs, Diagonalizations over polynomial time computable sets, Index sets and presentations of complexity classes, On the relative complexity of hard problems for complexity classes without complete problems, On closure properties of bounded two-sided error complexity classes, Gap-languages and log-time complexity classes, Honest polynomial time reducibilities and the \(P=?NP\) problem, A uniform approach to obtain diagonal sets in complexity classes, The p-T-degrees of the recursive sets: Lattice embeddings, extensions of embeddings and the two-quantifier theory, Diagonalization, uniformity, and fixed-point theorems, Nondiamond theorems for polynomial time reducibility, On computational complexity and honest polynomial degrees, Minimal pairs for P, The recursion-theoretic structure of complexity classes, Inhomogeneities in the polynomial-time degrees: The degrees of super sparse sets

Cites Work

• On the structure of sets in NP and other complexity classes
• On the Structure of Polynomial Time Reducibility