scientific article; zbMATH DE number 3869313

MaRDI QIDQ3337458zbMATH OpenFDO

Authors Klaus Ambos-Spies

Publication date 1984

zbMATH Keywords

embeddingTuring degreesrecursive setsNP-setsmany-one degreescountable distributive latticeupper semilattice of polynomial time degrees

Mathematics Subject Classification ID

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)

Recommendations

• Sublattices of the polynomial time degrees
• The p-T-degrees of the recursive sets: Lattice embeddings, extensions of embeddings and the two-quantifier theory
• scientific article; zbMATH DE number 62443
• On the embedding of distributive lattices into recursive polynomial degrees
• Logical Approaches to Computational Barriers

Cited in

(23)

• Honest polynomial time reducibilities and the \(P=?NP\) problem
• Inhomogeneities in the polynomial-time degrees: The degrees of super sparse sets
• Nondiamond theorems for polynomial time reducibility
• On \(\Pi_ 2\) theories of \(hp-T\) degrees of low sets
• Structures computable in polynomial time. I
• scientific article; zbMATH DE number 62443 (Why is no real title available?)
• The algebraic structure of the isomorphic types of tally, polynomial time computable sets
• scientific article; zbMATH DE number 3841832 (Why is no real title available?)
• Differences between resource bounded degree structures
• On MODkP Counting Degrees
• Uniformly hard languages.
• The p-T-degrees of the recursive sets: Lattice embeddings, extensions of embeddings and the two-quantifier theory
• Inhomogeneity of the p-s-Degrees of Recursive Functions
• Effectively dense Boolean algebras and their applications
• scientific article; zbMATH DE number 3963808 (Why is no real title available?)
• More on BPP and the polynomial-time hierarchy
• The structure of the honest polynomial m-degrees
• The theory of the polynomial many-one degrees of recursive sets is undecidable
• scientific article; zbMATH DE number 1390028 (Why is no real title available?)
• Degree-𝑑 chow parameters robustly determine degree-𝑑 PTFs (and algorithmic applications)
• Logical Approaches to Computational Barriers
• On the embedding of distributive lattices into recursive polynomial degrees
• Sublattices of the polynomial time degrees

This page was built for publication:

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