scientific article; zbMATH DE number 2163013

MaRDI QIDQ4673396zbMATH OpenFDO

Authors Holger Spakowski, Rahul Tripathi

Publication date 29 April 2005

zbMATH Keywords

complexity classesgap-definabilitypolynomial degree boundsrelativization theoryTuring hardness

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• RELATIVIZABLE AND NONRELATIVIZABLE THEOREMS IN THE POLYNOMIAL THEORY OF ALGORITHMS
• Quantitative Relativizations of Complexity Classes
• Relativizing relativized computations
• Strong separations of the polynomial hierarchy with oracles: Constructive separations by immune and simple sets
• Positive relativizations of the \(P=?\) NP problem

Cited in

(6)

• The structure of the honest polynomial m-degrees
• Degree estimates for polynomials constant on a hyperplane
• Quantum and classical complexity classes: Separations, collapses, and closure properties
• LWPP and WPP are not uniformly gap-definable
• A relationship between difference hierarchies and relativized polynomial hierarchies
• scientific article; zbMATH DE number 5592923 (Why is no real title available?)

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