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