Simulating probabilistic by deterministic algebraic computation trees (Q1821560): Difference between revisions

An Algebraic Computation Tree (ACT) is a computation model in which languages \(L\subset {\mathbb{R}}^ n\) for some fixed n can be recognized. In one step either an arithmetic operation from \(\{+,-,*,/)\) using input variables \(x_ i\), \(i\in \{1,...,n\}\), real constants, or previously computed values as operands can be executed, or a branching according to a predicate \(''p(x_ 1,...,x_ n)>0''\), where \(p(x_ 1,...,x_ n)\) is previously computed. In a probabilistic ACT (PACT) a fair coinflip can also be executed in a step. Two-sided errors are allowed, i.e. \((x_ 1,...,x_ n)\) is defined to be accepted (rejected), if it is accepted (rejected) with probability \(\geq 1-\epsilon\), \(\epsilon <\). The paper combines methods for proving lower bounds for ACT's from \textit{M. Ben Or}'s paper ''Lower bounds for algebraic computation trees'' [15th ACM Symp. Theory of Computing, 80-86 (1983)] and from \textit{C. H. Bennett} and \textit{J. Gill}'s paper in SIAM J. Comput. 10, 96-113 (1981; Zbl 0454.68030). It is shown that PACT's with complexity T can be simulated by ACT's with complexity \(O(T^ 2n)\).