John F. Canny
EECS Department
University of California, Berkeley
Technical Report No. UCB/CSD-88-439
August 1988
http://www2.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://www2.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://www2.eecs.berkeley.edu/Pubs/TechRpts/1988/6041.html %F Canny:CSD-88-439