scientific article; zbMATH DE number 4023249
[For the entire collection see Zbl 0587.00019.] We derive a recursion-theoretic result telling when a family of reductions to a class \({\mathcal A}\subseteq {\mathcal P}(\Sigma^*)\) can be replaced by a single oracle Turing machine. The theorem is a close analogue of the Uniform Boundedness Theorem of functional analysis, specializing it to the Cantor-set topology on \({\mathcal P}(\Sigma^*)\). This generalizes one of the main theorems of \textit{J. Grollmann} and \textit{A. Selman} [Complexity measures for public-key cryptosystems, Proc. FOCS '84], namely that \({\mathcal N}{\mathcal P}\)-hardness implies uniform \({\mathcal N}{\mathcal P}\)-hardness for `promise problems'. We investigate other consequences and problems arising from the theorem.
- 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
- 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)