On randomized semi-algebraic test complexity

DOI10.1006/jcom.1993.1016zbMath0806.68045OpenAlexW2032022602MaRDI QIDQ1260656

Marek Karpinski, Thomas Lickteig, Peter Bürgisser

Publication date: 24 August 1993

Published in: Journal of Complexity (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1006/jcom.1993.1016

zbMATH Keywords

randomized decision complexityrandomized decision trees

Mathematics Subject Classification ID

Semialgebraic sets and related spaces (14P10) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (5)

Semi-algebraic decision complexity, the real spectrum, and degree ⋮ A lower bound for randomized algebraic decision trees ⋮ Randomization and the computational power of analytic and algebraic decision trees ⋮ A tight lower bound for computing the diameter of a 3D convex polytope ⋮ On the decisional complexity of problems over the reals

This page was built for publication: On randomized semi-algebraic test complexity