This weeks student theory meeting

Thread View: ut.theory

1 messages

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

1 total messages Started by vincent Thu, 23 Nov 1989 19:06

#39

Author: vincent
Date: Thu, 23 Nov 1989 19:06

20 lines
1224 bytes

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

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