×

Simulating probabilistic by deterministic algebraic computation trees. (English) Zbl 0616.68051

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 M. Ben Or’s paper ”Lower bounds for algebraic computation trees” [15th ACM Symp. Theory of Computing, 80-86 (1983)] and from C. H. Bennett and 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)\).

MSC:

68Q05 Models of computation (Turing machines, etc.) (MSC2010)
68Q25 Analysis of algorithms and problem complexity

Citations:

Zbl 0454.68030

References:

[1] Bennett, C. H.; Gill, J., Relative to a random oracle, \(P^A\) ≠ \(NP^A\) ≠ co-\(NP^A\) with probability 1, SIAM J. Comput., 10, 96-113 (1981) · Zbl 0454.68030
[2] Ben Or, M., Lower bounds for algebraic computation trees, (15th ACM STOC (1983)), 80-86
[3] Dobkin, D.; Lipton, R. J., A lower bound of \(12n^2\) on linear search algorithms for the knapsack problem, J. Comput. System. Sci., 16, 413-416 (1978) · Zbl 0397.68045
[4] Feller, W., An Introduction to Probability Theory and its Applications (1957), Wiley: Wiley New York · Zbl 0155.23101
[5] Klein, P.; Meyer auf der Heide, F., A lower time bound for the knapsack problem on random access machines, Acta Inform., 19, 385-395 (1983) · Zbl 0515.68037
[6] Manber, U.; Tompa, M., Probabilistic, nondeterministic, and alternating decision trees, (14th ACM STOC (1982)), 234-244
[7] Meyer auf der Heide, F., Lower bounds for solving Diophantine equations on random access machines, J. ACM, 32, 4, 929-937 (1985) · Zbl 0633.68031
[8] Meyer auf der Heide, F., A polynomial linear search algorithm for the \(n\)-dimensional knapsack problem, J. ACM, 31, 3, 668-676 (1984) · Zbl 0631.68037
[9] Meyer auf der Heide, F., Fast algorithms for \(n\)-dimensional restrictions of hard problems, (17th ACM STOC (1985)), 413-420
[10] Milnor, J., Singular Points of Complex Hypersurfaces (1968), Princeton Univ. Press · Zbl 0184.48405
[11] Reif, J. H., On synchronous parallel computations with independent probabilistic choice, SIAM J. Comput., 13, 1, 46-56 (1984) · Zbl 0558.68038
[12] Reingold, E., On the optimality of some set algorithms, J. ACM, 19, 649-659 (1972) · Zbl 0246.68008
[13] Snir, M., Lower bounds for probabilistic linear decision trees, (Res. Rept. 83-6 (1983), Dept. of Computer Science, Hebrew Univ. of Jerusalem: Dept. of Computer Science, Hebrew Univ. of Jerusalem Israel) · Zbl 0581.68042
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.