scientific article; zbMATH DE number 3869313

zbMATH Open0546.03021MaRDI QIDQ3337458FDOQ3337458

Authors: Klaus Ambos-Spies 

Publication date: 1984

Title of this publication is not available (Why is that?)

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

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)

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
• Title not available (Why is that?)
• The algebraic structure of the isomorphic types of tally, polynomial time computable sets
• Title not available (Why is that?)
• 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
• Title not available (Why is that?)
• 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
• Title not available (Why is that?)
• 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)