文章基本信息

标题：Polynomial Time with Restricted Use of Randomness
本地全文：下载
作者：Matei David ; Periklis Papakonstantinou ; Anastasios Sidiropoulos 等
期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2009
卷号：2009
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：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 parametrize these machines by allowing at most r(N)-1 reversals on the random tape, thus obtaining the r(N)-th level of our hierarchy, denoted by RPdL[r]. It follows by a result of Cook [Coo71] that RPdL[1]=P, and of Ruzzo [Ruz81] that RPdL[exp(N)]=RP. Our main results are the following. - For every i>=1, derandomizing RPdL[2^{O(log^i N)}] implies the derandomization of RNC^i. Thus, progress towards the P vs RP question along our hierarchy implies also progress towards derandomizing RNC. Perhaps more surprisingly, we also prove a partial converse: Pseurorandom generators (PRGs) for RNC^(i+1) are sufficient to derandomize RPdL[2^{O(log^i N)}]; i.e. derandomizing using PRGs a class believed to be strictly inside P, we derandomize a class containing P. More generally, we introduce Randomness Compilers, a model equivalent to Stack Machines. In this model a polynomial time algorithm gets an input x and it outputs a circuit C_x, which takes random inputs. Acceptance of x is determined by the acceptance probability of C_x. When C_x is of polynomial size and depth O(log^i N) the corresponding class is denoted by P+RNC^i, and we show that RPdL[2^{O(log^i N)}]\subseteq P+RNC^i \subseteq RPdL[2^{O(log^{i+1} N)}]. - We show an unconditional N^Omega(1) lower bound on the number of reversals required by a SM for Polynomial Evaluation. This in particular implies that known Schwartz-Zippel-like algorithms for Polynomial Identity Testing cannot be implemented in the lowest levels of our hierarchy. - We show that in the 1-st level of our hierarchy, machines with one-sided error are as powerful as machines with two-sided and unbounded error.
关键词：Communication complexity , complexity hierarchy , derandomization , polynomial identity testing , probabilistic polynomial time