ECCC-Report TR03-036https://eccc.weizmann.ac.il/report/2003/036Comments and Revisions published for TR03-036en-usFri, 30 May 2003 20:55:13 +0300
Paper TR03-036
| Polynomial equation elimination via Tarski Algebra |
Bruce Edward Litow
https://eccc.weizmann.ac.il/report/2003/036The 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
Fri, 30 May 2003 20:55:13 +0300https://eccc.weizmann.ac.il/report/2003/036