Simulating probabilistic by deterministic algebraic computation trees
type: Item
instance of: scholarly article
title: Simulating probabilistic by deterministic algebraic computation trees
zbMATH Open document ID: 0616.68051
DOI: 10.1016/0304-3975(85)90079-9
author: Friedhelm Meyer auf der Heide
published in: Theoretical Computer Science
publication date: 1985-01-01T00:00:00Z
full work available at URL: urn:nbn:de:hbz:466:2-5988
review text: 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)\).
Mathematics Subject Classification ID: 68Q05
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 3999298
zbMATH Keywords: Algebraic Computation Tree
zbMATH Keywords: computation model
zbMATH Keywords: probabilistic ACT
zbMATH Keywords: fair coinflip
MaRDI profile type: Publication
OpenAlex ID: W2161824925
cites work: Relative to a Random OracleA, ${\bf P}^A \ne {\bf NP}^A \ne \text{co-}{\bf NP}^A $ with Probability 1
cites work: A lower bound of \({1\over 2}n^2\) on linear search programs for the knapsack problem
cites work: Q5538132
cites work: A lower time bound for the knapsack problem on random access machines
cites work: Lower bounds for solving linear diophantine equations on random access machines
cites work: A Polynomial Linear Search Algorithm for the n -Dimensional Knapsack Problem
cites work: Singular Points of Complex Hypersurfaces. (AM-61)
cites work: On Synchronous Parallel Computations with Independent Probabilistic Choice
cites work: On the Optimality of Some Set Algorithms
cites work: Lower bounds on probabilistic linear decision trees
description: scientific article; zbMATH DE number 3999298