THEORY SEMINAR

Thread View: ont.events

1 messages

[T] Back to Threads [V] Tree View [G] Group Articles

1 total messages Started by wlrush Thu, 12 Nov 1992 21:16

#293

Author: wlrush
Date: Thu, 12 Nov 1992 21:16

41 lines
1752 bytes

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.

Thread Navigation

This is a paginated view of messages in the thread with full content displayed inline.

Messages are displayed in chronological order, with the original post highlighted in green.

Use pagination controls to navigate through all messages in large threads.

Back to All Threads