Sublattices of the polynomial time degrees

DOI10.1016/S0019-9958(85)80020-6zbMath0556.03033MaRDI QIDQ3220572

Ambos-Spies, Klaus

Publication date: 1985

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

Full work available at URL: https://doi.org/10.1016/s0019-9958(85)80020-6

zbMATH Keywords

distributive lattice; reducibilities; polynomial time degrees of recursive sets

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

03D15: Complexity of computation (including implicit computational complexity)

03D20: Recursive functions and relations, subrecursive hierarchies

03D30: Other degrees and reducibilities in computability and recursion theory

Related Items

Exact Pairs for Abstract Bounded Reducibilities, The theory of the polynomial many-one degrees of recursive sets is undecidable, Decidability of the two-quantifier theory of the recursively enumerable weak truth-table degrees and other distributive upper semi-lattices, A characterization of the leaf language classes, Honest polynomial time reducibilities and the \(P=?NP\) problem, On the relative complexity of hard problems for complexity classes without complete problems, The p-T-degrees of the recursive sets: Lattice embeddings, extensions of embeddings and the two-quantifier theory, The structure of the honest polynomial m-degrees, Gap-languages and log-time complexity classes, Structural properties of bounded relations with an application to NP optimization problems, Constructing NP-intermediate problems by blowing holes with parameters of various properties, A complexity theory for feasible closure properties, On the structures inside truth-table degrees