scientific article; zbMATH DE number 1390028

MaRDI QIDQ4934293zbMATH OpenFDO

Authors Klaus Ambos-Spies

Publication date 27 July 2000

zbMATH Keywords

complexitydegreelattice embeddingslocal structurep-m-degreep-r-degreep-T-degreepolynomial time reducibilitiespolynomials time degree

Mathematics Subject Classification ID

Research exposition (monographs, survey articles) pertaining to mathematical logic and foundations (03-02) Complexity of computation (including implicit computational complexity) (03D15) Other degrees and reducibilities in computability and recursion theory (03D30) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• Strong polynomial-time reducibility
• scientific article; zbMATH DE number 3869313
• Logical Approaches to Computational Barriers
• Nondiamond theorems for polynomial time reducibility
• Publication:4934278

Cited in

(11)

• Nondiamond theorems for polynomial time reducibility
• Polynomial time introreducibility
• Weak completeness notions for exponential time
• scientific article; zbMATH DE number 3963808 (Why is no real title available?)
• scientific article; zbMATH DE number 62443 (Why is no real title available?)
• scientific article; zbMATH DE number 1115674 (Why is no real title available?)
• scientific article; zbMATH DE number 7577584 (Why is no real title available?)
• Logical Approaches to Computational Barriers
• Strong polynomial-time reducibility
• Undecidability of the degree structure of primitive recursive m-reducibility
• Computably enumerable equivalence relations via primitive recursive reductions

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 Q4934293)