The complexity of problems on probabilistic, nondeterministic, and alternating decision trees

DOI10.1145/3828.3838zbMath0631.68044OpenAlexW2065230093MaRDI QIDQ3768402

Martin Tompa, Udi Manber

Publication date: 1985

Published in: Journal of the ACM (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/3828.3838

zbMATH Keywords

lower boundsMonte Carlo algorithmsdecision treesalternating Turing machine

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Algorithms in computer science (68W99)

Related Items (11)

A probabilistic distributed algorithm for set intersection and its analysis ⋮ Geometric complexity of some location problems ⋮ Obtaining lower bounds using artificial components ⋮ A lower bound for randomized algebraic decision trees ⋮ Randomization and the computational power of analytic and algebraic decision trees ⋮ Decomposing probabilistic lambda calculi ⋮ COMPUTING LARGEST CIRCLES SEPARATING TWO SETS OF SEGMENTS ⋮ Decision trees: Old and new results. ⋮ On the decisional complexity of problems over the reals ⋮ Unnamed Item ⋮ Lower bounds to randomized algorithms for graph properties

This page was built for publication: The complexity of problems on probabilistic, nondeterministic, and alternating decision trees