On randomized algebraic test complexity
Peter B urgisser, Marek Karpiński, Thomas Lickteig · 1992
We investigate the impact of randomization on the complexity of deciding membership in a (semi-)algebraic subset $X \subset \rr^m$. Examples are exhibited where allowing for a certain error probability $\epsilon$ in the answer of the algorithms the complexity of decision problems decreases. A randomized $(\Omega^k,\{=,\leq\})$-decision tree ($k \subseteq\rr$ a subfield) over $m$ will be defined as a pair $(T,\mu)$ where $\mu$ a probability measure on some $\rr^n$ and $T$ is a $(\Omega^k,\{=,\leq\})$-decision tree over $m+n$. We prove a general lower bound on the average decision complexity for testing membership in an irreducible algebraic subset $X \subset \rr^m$ and apply it to $k$-generic complete intersection of polynomials of the same degree, extending results in [4, 6]. We also give applications to nongeneric cases, such as graphs of elementary symmetric functions, $\mbox{SL}(m,\rr)$, and determinant varieties, extending results in \cite{Li:90}.