Polynomial Time with Restricted Use of Randomness
Matei David, Periklis A. Papakonstantinou, Anastasios Sidiropoulos · Electronic colloquium on computational complexity · 2009
We define a hierarchy of complexity classes that lie between P and RP, yielding a new way of quantifying partial progress towards the derandomization of RP. A standard approach in derandomization is to reduce the number of random bits an algorithm uses. We instead focus on a model of computation that allows us to quantify the extent to which random bits are being used. More specifically, we consider Stack Machines (SMs), which are log-space Turing Machines that have access to an unbounded stack, an input tape of length N , and a random tape of length N O(1) . We parameterize these machines by al