Simulating probabilistic by deterministic algebraic computation trees

DOI10.1016/0304-3975(85)90079-9zbMath0616.68051OpenAlexW2161824925MaRDI QIDQ1821560

Friedhelm Meyer auf der Heide

Publication date: 1985

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: http://nbn-resolving.de/urn:nbn:de:hbz:466:2-5988

zbMATH Keywords

computation modelAlgebraic Computation Treefair coinflipprobabilistic ACT

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Related Items (6)

Nearly sharp complexity bounds for multiprocessor algebraic computations ⋮ A lower bound for randomized algebraic decision trees ⋮ Randomization and the computational power of analytic and algebraic decision trees ⋮ On genuinely time bounded computations ⋮ Decision trees: Old and new results. ⋮ On the decisional complexity of problems over the reals

Cites Work

• Unnamed Item
• A lower time bound for the knapsack problem on random access machines
• Lower bounds on probabilistic linear decision trees
• A lower bound of \({1\over 2}n^2\) on linear search programs for the knapsack problem
• On Synchronous Parallel Computations with Independent Probabilistic Choice
• A Polynomial Linear Search Algorithm for the n -Dimensional Knapsack Problem
• Lower bounds for solving linear diophantine equations on random access machines
• Relative to a Random OracleA, ${\bf P}^A \ne {\bf NP}^A \ne \text{co-}{\bf NP}^A $ with Probability 1
• Singular Points of Complex Hypersurfaces. (AM-61)
• On the Optimality of Some Set Algorithms

This page was built for publication: Simulating probabilistic by deterministic algebraic computation trees