scientific article; zbMATH DE number 3869313

MaRDI QIDQ3337458zbMATH OpenFDO

Authors Klaus Ambos-Spies

Publication date 1984

zbMATH Keywords

countable distributive latticeembeddingmany-one degreesNP-setsrecursive setsTuring degreesupper 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

(24)

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

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)