Computational complexity of recursively enumerable sets

DOI10.1016/S0019-9958(82)80082-XMaRDI QIDQ4750632zbMATH OpenFDO

Authors Robert I. Soare

Publication date 1982

Published in Information and Control (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/S0019-9958(82)80082-X

zbMATH Keywords

complexity measuredegreerecursively enumerable sets

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Recursively (computably) enumerable sets and degrees (03D25)

Cited in

(6)

• Lower bounds on degrees of game-theoretic structures
• Index sets related to prompt simplicity
• On computational complexity and honest polynomial degrees
• An Algebraic Decomposition of the Recursively Enumerable Degrees and the Coincidence of Several Degree Classes with the Promptly Simple Degrees
• The Quotient Semilattice of the Recursively Enumerable Degrees Modulo the Cappable Degrees
• Implicit measurements of dynamic complexity properties and splittings of speedable sets

This page was built for publication: Computational complexity of recursively enumerable sets

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