ylfink@water.UUCP (ylfink) (02/18/86)
DEPARTMENT OF COMPUTER SCIENCE
UNIVERSITY OF WATERLOO
SEMINAR ACTIVITIES
COMPUTER SCIENCE COLLOQUIUM
- Thursday, February 20, 1986.
Professor Scott McCallum of the University of Toronto
will speak on ``Decision Methods for Algebraic Equa-
tions''.
TIME: 2:30 PM
ROOM: MC 2034
ABSTRACT
The decision problem for systems of polynomial equali-
ties and inequalities in ``n'' variables with rational
co-efficients is to decide whether or not a given such
system has a solution in real n-space. An algorithm
due to Collins for this decision problem will be
presented in this talk. The algorithm has been imple-
mented in the SAC-2 computer algebra system. For
``n''-fixed, the algorithm runs in polynomial time.
However, the running time depends doubly-exponentially
on ``n''. A recent algorithm for the decision problem
due to Grigoriev runs in time singularly-exponential in
``n''.