scientific article; zbMATH DE number 4189714

MaRDI QIDQ5753945zbMATH OpenFDO

Authors Klaus Ambos-Spies, S. Homer, Dongping Yang

Publication date 1990

zbMATH Keywords

EXPTALLY setshonest reductionsmany-one reducibilitiesminimal degreesoraclestructural complexity

Mathematics Subject Classification ID

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

• Honest polynomial degrees and \(P=?NP\)
• Minimal degrees for polynomial reducibilities
• Honest polynomial time reducibilities and the \(P=?NP\) problem
• The existence of minimal honest polynomial degree below and recursively enumerable degrees
• Strong minimal pair theorem for the honest polynomial degrees of \(\Delta{}^ 0_ 2\) low sets

Cited in

(5)

• Honest polynomial degrees and \(P=?NP\)
• The structure of the honest polynomial m-degrees
• Uniformly hard languages.
• Minimal degrees for polynomial reducibilities
• Honest polynomial time reducibilities and the \(P=?NP\) problem

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