scientific article; zbMATH DE number 4023249

MaRDI QIDQ3765753zbMATH OpenFDO

Authors Kenneth W. Regan

Publication date 1986

zbMATH Keywords

\({\mathcal N}{\mathcal P}\)-hardnessCantor-set topologyoracle Turing machinepromise problemsUniform Boundedness Theorem

Mathematics Subject Classification ID

Turing machines and related notions (03D10) Complexity of computation (including implicit computational complexity) (03D15) Other degrees and reducibilities in computability and recursion theory (03D30) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• A uniform version of Jarník's theorem
• Generalization of the Bylov reducibility theorem and some applications
• A generalization of Hall-Higman's reduction theorem
• A uniform version of a theorem by Dvir and Moran
• scientific article; zbMATH DE number 3911288
• An extension of a theorem of Fulkerson and Gross
• A reduction theorem for the Galois–McKay conjecture
• Uniform generalizations of Fueter's theorem
• Borel-piecewise continuous reducibility for uniformization problems
• A new proof of the uniformization theorem

Cited in

(6)

• Diagonalization, uniformity, and fixed-point theorems
• Hard promise problems and nonuniform complexity
• The Complexity of Complexity
• scientific article; zbMATH DE number 18529 (Why is no real title available?)
• scientific article; zbMATH DE number 845926 (Why is no real title available?)
• Kolmogorov complexity characterizes statistical zero knowledge

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