Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR03-036 | 27th April 2003 00:00

Polynomial equation elimination via Tarski Algebra


Authors: Bruce Edward Litow
Publication: 30th May 2003 20:55
Downloads: 1195


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

ISSN 1433-8092 | Imprint