A higher-order characterization of probabilistic polynomial time (Q2343130): Difference between revisions

In the paper under review the authors present a calculus called RSLR (Random Safe Linear Recursion) which is an implicit higher-order characterization of the class of those problems that can be decided in probabilistic polynomial time with error probability smaller than \(\frac{1}{2}\). Earlier, \textit{S. Bellantoni} and \textit{S. Cook} [Comput. Complexity 2, No. 2, 97--110 (1992; Zbl 0766.68037)] defined a scheme SR (Safe Recursion) which gives a recursion-theoretic characterization of the polytime functions. Later, \textit{M. Hofmann} [Lect. Notes Comput. Sci. 1414, 275--294 (1998; Zbl 0908.03022)] defined a new scheme SLR (Safe Linear Recursion) which is a generalization of Bellantoni and Cook's Safe Recursion and in which the linearity plays a crucial role. The authors' system RSLR is obtained by endowing SLR with a new primitive for random binary choice. In the last two sections of the paper the authors establish a precise correspondence between RSLR and probabilistic polynomial time Turing machines.