scientific article; zbMATH DE number 3869313
From MaRDI portal
Publication:3337458
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
embeddingTuring degreesrecursive setsNP-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)
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)