Path: utzoo!attcan!utgpu!jarvis.csri.toronto.edu!neat.cs.toronto.edu!vincent
From: vincent@cs.toronto.edu
Newsgroups: ut.theory
Subject: This weeks student theory meeting
Message-ID: <89Nov23.140544est.2836@neat.cs.toronto.edu>
Date: 23 Nov 89 19:06:24 GMT
Lines: 20


			Student Theory Meeting
	This week's theory meeting will be held in the Seminar Room
(SF 3207) at 3pm, Friday. This week Pekka Orponen will give a talk
on the structural complexity of problems.

			ABSTRACT
We introduce a measure for the computational complexity of
individual instances of a computational problem and study
its properties. Intuitively, instances solved quickly by
small special-case programs are easy, whereas instances
whose solution in a given time limit requires a large
program (or, trivially, table look-up) are hard.

Formalizing this idea we obtain, among other things, natural
characterizations of the class P and the class of P-immune sets.
Further results include: the complexity of SAT instances grows
at a logarithmic rate iff P = NP, and if EXPTIME \neq NEXPTIME,
then SAT has infinitely many "hard" instances (i.e., ones that
cannot be solved quickly essentially better than by table look-up).