Abstract:
The elimination problem is classical: implicitly express one of the variables occurring in a finite system of polynomial equations as an algebraic function of a designated subset of the remaining variables. Solutions to this problem by resultants, or more comprehensively by use of Gr\"{o}bner basis methods are available. In this paper we show under an assumption that a very direct solution can be carried out using Tarski algebra. The Tarski algebra approach has two advantages over other, more involved methods. First, it allows for the direct determination of the possibility of eliminating variables in terms of deciding a single sentence. Second, assuming that a deep result of Grigoriev can be extended from sentences to formulas of Tarski algebra, the algorithm we present is in EXPTIME, while other methods are so far only known to have a doubly exponential worst case running tim