Some algebraic and geometric computations in PSPACE

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.

REFERENCES

• BKR: Michael Ben-Or , Dexter Kozen , John Reif, The complexity of elementary algebra and geometry, Journal of Computer and System Sciences, v.32 n.2, p.251-264, April 1986 [doi>10.1016/0022-0000(86)90029-2]
• BT: W. S. Brown , J. F. Traub, On Euclid's Algorithm and the Theory of Subresultants, Journal of the ACM (JACM), v.18 n.4, p.505-514, Oct. 1971 [doi>10.1145/321662.321665]
• C87a: John Canny, Exact solution of some robot motion planning problems, on The fourth international symposium, p.505-513, May 1988, Univ. of California, Santa Clara, California, United States
• C87b: Canny J. F., "A New Algebraic Met}rod for Motion PlanltiIlg and Real Geo,netry", Pr()c. 28th IEEE symp. FOCS, Los Angeles, (1987), pp 39-48.
• C88a: Canny J. F., "Generalized Characteristic Polyno- PlanltiIlg and Real Geo,netry", Pr()c. 28th IEEE (July 1988).
• C88b: John F. Canny, The complexity of robot motion planning, MIT Press, Cambridge, MA, 1988
• Col: George E. Collins, Hauptvortrag: Quantifier elimination for real closed fields by cylindrical algebraic decomposition, Proceedings of the 2nd GI Conference on Automata Theory and Formal Languages, p.134-183, May 20-23, 1975
• Csa: ('sanky L., "Fast Parallel Matrix Inversion Algori)h~s" SIAM J. Comp., Vol. 5, No. 4, (Dec. 1976) pp 6 t 8-623.
• GWD: Gibson C. G., Wirthmiiller K., Du Plessis A. A., Looijenga E. J. N., "Topological Stability of Smooth Mappings", Lecture Notes in Mathematics, No. 552, Springer-Verlag, New York, (1976).
• GG: Guilleman V., and Golubitsky M., "Stable Map- Smooth Mappings", Lecture Notes in Mathemat- Verlag, New York, (it.)7:~).
• GV: Grigoryev D. Y. and Vorobjov N. N., "Solving Systems of Polynomial Inequalities in Subexponential tion in NC", Proc 25th IEEE Syrup. FOCS, (1985), on decision algorithms for the theory of real chased tields, to ~ppear (1988).
• KY: Kozen D., and Yap C. "Algebraic Cell Deco~nposition in NC", Proc 25th IEEE Syrup. FOCS, (1985), pp. 515-521.
• Loz: Lozam)-P6rez T., "Spatial Plauning: A (;onfigurati(m Space AI)pro,wh," IEEE Trans. (~oltipttters, ('-3'2, N~) '2 {Feb 1983), pp 108-t20.
• Mig: Mignotte M., "Some Useful Bounds", in "Computer Algebra, Symbolic and Algebraic Computatiox~", Buchberger et al. ed., Springer-Verlag, New Y,)rk, (1982).
• Rei: Reif J., "Complexity of the Mover's Problem and Preseuce of Movisig Obstt~cles", Pr(,c. 25tit {EEE (1979).
• RS: Reif J., and Sharir M., "Motion Planning in the Preseuce of Movisig Obstt~cles", Pr(,c. 25tit {EEE Syrup. FOCS, (1985), pp. t44-t54.
• RSt: Reif J., and Storer J., "Shortest Paths in Euclidean Space with Polyhedral Obstacles", Tech. Rep. CS- 85-121, Comp. Sci. Dept., Brandeis University, ( April 1985).
• Ren: Renegar J., "On the Worst-Case Arithmetic Co{nplexity of Approximating Zeros of Systems of Polynomials'', Technical Report, School of Operations Research and industrial Engineering, Cornell University, (May 1937).
• SS: Schwartz J. and Sharir M., "On the 'Piano M,)vers' Problem, I!. General Techniques for (.:'o~nt>uting Topological Properties of Real Algebraic mani folds," Computer Science Department, New York University report 41, (1982).
• SSc: Micha Sharir( , Amir Schorr, On shortest paths in polyhedral spaces, Proceedings of the sixteenth annual ACM symposium on Theory of computing, p.144-153, December 1984 [doi>10.1145/800057.808676]
• Wae: van der Waerden B. L., "Modern Algebra". (third edition) F. Ungar Publishing Co.. New York (1950).

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems
          Subjects: Computations on polynomials

Additional Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE

General Terms:
Algorithms, Theory