Some Algebraic and Geometric Computations in PSPACE
John F. Canny
EECS Department
University of California, Berkeley
Technical Report No. UCB/CSD-88-439
August 1988
http://www.eecs.berkeley.edu/Pubs/TechRpts/1988/CSD-88-439.pdf
We give a PSPACE algorithm for determining the signs of multivariate polynomials at the common zeros of a system of polynomial equations. One of the consequences of this result is that the "Generalized Movers' Problem" in robotics drops from EXPTIME into PSPACE, and is therefore PSPACE-complete by a previous hardness result [Rei]. We also show that the existential theory of the real numbers can be decided in PSPACE. Other geometric problems that also drop into PSPACE include the 3-d Euclidean Shortest Path Problem, and the "2-d Asteroid Avoidance Problem" described in [RS]. Our method combines the theorem of the primitive element from classical algebra with a symbolic polynomial evaluation lemma from [BKR]. A decision problem involving several algebraic numbers is reduced to a problem involving a single algebraic number or primitive element, which rationally generates all the given algebraic numbers.
BibTeX citation:
@techreport{Canny:CSD-88-439,
Author = {Canny, John F.},
Title = {Some Algebraic and Geometric Computations in PSPACE},
Institution = {EECS Department, University of California, Berkeley},
Year = {1988},
Month = {Aug},
URL = {http://www.eecs.berkeley.edu/Pubs/TechRpts/1988/6041.html},
Number = {UCB/CSD-88-439},
Abstract = {We give a PSPACE algorithm for determining the signs of multivariate polynomials at the common zeros of a system of polynomial equations. One of the consequences of this result is that the "Generalized Movers' Problem" in robotics drops from EXPTIME into PSPACE, and is therefore PSPACE-complete by a previous hardness result [Rei]. We also show that the existential theory of the real numbers can be decided in PSPACE. Other geometric problems that also drop into PSPACE include the 3-d Euclidean Shortest Path Problem, and the "2-d Asteroid Avoidance Problem" described in [RS]. Our method combines the theorem of the primitive element from classical algebra with a symbolic polynomial evaluation lemma from [BKR]. A decision problem involving several algebraic numbers is reduced to a problem involving a single algebraic number or primitive element, which rationally generates all the given algebraic numbers.}
}
EndNote citation:
%0 Report %A Canny, John F. %T Some Algebraic and Geometric Computations in PSPACE %I EECS Department, University of California, Berkeley %D 1988 %@ UCB/CSD-88-439 %U http://www.eecs.berkeley.edu/Pubs/TechRpts/1988/6041.html %F Canny:CSD-88-439