Sublattices of the polynomial time degrees
From MaRDI portal
Publication:3220572
DOI10.1016/S0019-9958(85)80020-6zbMath0556.03033OpenAlexW1970624740MaRDI QIDQ3220572
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
Analysis of algorithms and problem complexity (68Q25) Complexity of computation (including implicit computational complexity) (03D15) Recursive functions and relations, subrecursive hierarchies (03D20) Other degrees and reducibilities in computability and recursion theory (03D30)
Related Items (13)
A complexity theory for feasible closure properties ⋮ A characterization of the leaf language classes ⋮ Exact Pairs for Abstract Bounded Reducibilities ⋮ The structure of the honest polynomial m-degrees ⋮ On the relative complexity of hard problems for complexity classes without complete problems ⋮ The theory of the polynomial many-one degrees of recursive sets is undecidable ⋮ Gap-languages and log-time complexity classes ⋮ Honest polynomial time reducibilities and the \(P=?NP\) problem ⋮ Decidability of the two-quantifier theory of the recursively enumerable weak truth-table degrees and other distributive upper semi-lattices ⋮ The p-T-degrees of the recursive sets: Lattice embeddings, extensions of embeddings and the two-quantifier theory ⋮ On the structures inside truth-table degrees ⋮ Structural properties of bounded relations with an application to NP optimization problems ⋮ Constructing NP-intermediate problems by blowing holes with parameters of various properties
This page was built for publication: Sublattices of the polynomial time degrees
