scientific article
From MaRDI portal
Publication:3337458
zbMath0546.03021MaRDI QIDQ3337458
Publication date: 1984
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
embeddingrecursive setsTuring degreesNP-setsmany-one degreescountable distributive latticeupper semilattice of polynomial time degrees
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
Uniformly hard languages., On MODkP Counting Degrees, The theory of the polynomial many-one degrees of recursive sets is undecidable, On the embedding of distributive lattices into recursive polynomial degrees, Honest polynomial time reducibilities and the \(P=?NP\) problem, The p-T-degrees of the recursive sets: Lattice embeddings, extensions of embeddings and the two-quantifier theory, Nondiamond theorems for polynomial time reducibility, Effectively dense Boolean algebras and their applications, On \(\Pi_ 2\) theories of \(hp-T\) degrees of low sets, Inhomogeneities in the polynomial-time degrees: The degrees of super sparse sets
