scientific article; zbMATH DE number 1390028

zbMATH Open0941.03043MaRDI QIDQ4934293FDOQ4934293

Authors: Klaus Ambos-Spies 

Publication date: 27 July 2000

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

Recommendations

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

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)

Cited In (8)

• Nondiamond theorems for polynomial time reducibility
• Title not available (Why is that?)
• Polynomial time introreducibility
• Weak completeness notions for exponential time
• Title not available (Why is that?)
• Title not available (Why is that?)
• Logical Approaches to Computational Barriers
• Strong 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)