On the theory of the PTIME degrees of the recursive sets

DOI10.1016/0022-0000(90)90024-FzbMath0715.68040MaRDI QIDQ751819

Juichi Shinoda, Theodore A. Slaman

Publication date: 1990

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

zbMATH Keywords

recursive setsfirst order theoriesPTIME degrees

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Complexity of computation (including implicit computational complexity) (03D15) Recursively (computably) enumerable sets and degrees (03D25)

Related Items

Uniformly hard languages., A characterization of the leaf language classes, Exact Pairs for Abstract Bounded Reducibilities, The theory of the polynomial many-one degrees of recursive sets is undecidable, Automorphisms in the PTIME-Turing degrees of recursive sets, Nondiamond theorems for polynomial time reducibility, Differences between resource bounded degree structures, The Role of True Finiteness in the Admissible Recursively Enumerable Degrees, THE THEORY OF THE METARECURSIVELY ENUMERABLE DEGREES, Effectively dense Boolean algebras and their applications

Cites Work

• Unnamed Item
• On degrees of recursive unsolvability
• Definability in the Turing degrees
• The upper semi-lattice of degrees of recursive unsolvability
• The undecidability of the recursively enumerable degrees
• The Theory of the Degrees below 0 ′
• Reducibility orderings: Theories, definability and automorphisms
• On the Structure of Polynomial Time Reducibility
• Recursively enumerable sets and degrees