A note on Rabin's width of a complete proof (Q1327592)

The concept of generic width of a semi-algebraic set is introduced and used to obtain various lower bounds for decisional complexities. Rabin considered the optimality of algorithms solving the membership problem for convex sets defined by the simultaneous positivity of linear forms and gave several applications. In the paper, a rigorous proof of a theorem of Rabin is given and insufficiencies in the original Rabin's proof are discussed (it is not true that the closure of a semi-algebraic set can be simply defined by relaxing inequalities on the polynomials defining it). The method presented in the paper has new applications to more general situations than linear ones. Convincing lower bounds for several important decision problems in real algebraic geometry (like the existence of a real root) or in computational geometry (directed oriented convex problem) are obtained.