Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Posting-Version: version B 2.10.2 9/18/84; site water.UUCP
Path: utzoo!watmath!watnot!water!ylfink
From: ylfink@water.UUCP (ylfink)
Newsgroups: ont.events
Subject: UW CS Colloq. Semi., Prof. McCallum on "Decision Methods for Algebraic Equations".
Message-ID: <225@water.UUCP>
Date: Tue, 18-Feb-86 10:39:32 EST
Article-I.D.: water.225
Posted: Tue Feb 18 10:39:32 1986
Date-Received: Wed, 19-Feb-86 00:55:30 EST
Expires: Fri, 21-Feb-86 00:00:00 EST
Organization: U of Waterloo, Ontario
Lines: 31


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''.