Semi-algebraic decision complexity, the real spectrum, and degree Original Research Article

Semi-algebraic decision complexity introduces a quantitative finiteness aspect into semi-algebraic geometry. In this paper we combine methods from abstract real algebraic geometry and complexity theory in order to show lower bounds on the arithmetical cost of semi-algebraic decision trees. In contrast to the topological combinatorial methods the approach is local and based on the relations computed along paths distinguished by certain well defined points in the real spectrum of the polynomial ring R[X1, …,Xn]. We describe the theme of semi-algebraic decision trees entirely from the point of view of the concept of the real spectrum which extracts the local “quintessence” of the behavior of decision trees. Together with the degree argument —introduced into complexity theory by Strassen [46] — we obtain bounds that apply to concrete natural problems, and their range of application complements the one of topologically based lower bounds. Various new applications to test problems around interpolation (solvability of overdetermined interpolation tasks) and Chinese remaindering are included.