John F. Canny

EECS Department, University of California, Berkeley

Technical Report No. UCB/CSD-88-439

, 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},
    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