🚀 go-pugleaf

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