scientific article; zbMATH DE number 1390028

MaRDI QIDQ4934293zbMATH OpenFDO

Authors Klaus Ambos-Spies

Publication date 27 July 2000

zbMATH Keywords

complexitylocal structuredegreelattice embeddingspolynomial time reducibilitiesp-m-degreep-r-degreep-T-degreepolynomials time degree

Mathematics Subject Classification ID

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

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

(8)

• scientific article; zbMATH DE number 62443 (Why is no real title available?)
• scientific article; zbMATH DE number 3963808 (Why is no real title available?)
• Logical Approaches to Computational Barriers
• Polynomial time introreducibility
• Strong polynomial-time reducibility
• Weak completeness notions for exponential time
• scientific article; zbMATH DE number 7577584 (Why is no real title available?)
• Nondiamond theorems for polynomial time reducibility

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)