ISSN:
1420-8954
Keywords:
Algebraic complexity theory
;
decisional complexity
;
semialgebraic sets
;
width of a complete proof
;
generic width of a semialgebraic set
;
68Q25
;
68Q40
;
14P20
;
14P10
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
Notes:
Abstract We introduce and analyze the concept of generic width of a semialgebraic set, showing that it gives lower bounds for decisional complexities. By means of the computation of the generic width we are able to solve rigorously the complexity problems posed by M.O. Rabin in [10], such as optimization of linear mappings on finite sets. We show that the results on the generic width can also be applied to obtain lower bounds for problems which in general do not admit a linear mapping description, such as optimization of polynomial mappings on finite sets, existence of a real root, finite selection and subset decision, or the direct oriented-convex hull problem introduced by J. Jaromczyk in [8].
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF01205053
Permalink