__
TR03-036 | 27th April 2003 00:00
__

#### Polynomial equation elimination via Tarski Algebra

**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