scientific article; zbMATH DE number 4023249

From MaRDI portal
Publication:3765753





[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.











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)