🚀 go-pugleaf

DEPARTMENT OF COMPUTER SCIENCE
UNIVERSITY OF WATERLOO
SEMINAR ACTIVITIES

THEORY SEMINAR

                    -Wednesday, November 18, 1992

Cristian  Calude,  Computer  Science Dept., Western Ontario &
University  of  Auckland,  New  Zealand  will  speak on
"Topological Methods In  Complexity Theory"

TIME:                 1:30-2:30 p.m.

ROOM:                 DC 1304

ABSTRACT

The  separation of various classes of sets/functions is
an important objective in complexity theory.  We survey
some  recent  results of this type mainly obtained with
the   aid  of  a  constructive  version  of  the  Baire
classification method.  Problems in abstract complexity
(Blum),   and  structural  complexity  and  algorithmic
information theory (Chaitin) will be discussed.

Typical questions include:

1.  How many computable functions are speedable?

2.  How  large  is  the  set NP - P, in case it is non-
    empty?

3.  How many strings/sequences are random?

Related   questions   pertaining   the  foundations  of
(feasible)  mathematics [given a reasonably axiomatized
theory  T,  how  'likely'  is it that a true statement,
picked  at  random, cannot be proved within T?] will be
also discussed.