16.3.2007 HIIT seminar

HIIT seminars in spring 2007 will be held in hall **B222** of Exactum,
on Fridays starting at 10:15 a.m. Coffee available from 10.

Fri Mar 16
Kerkko Luosto
Quantifiers and low level complexity

Abstract:
Computational complexity theory is interested in various resources which are needed to solve computational problems. For natural reasons, the emphasis has traditionally been on time and space resources. An alternative approach, descriptive complexity theory, is to study the logical resources. This entails that data is identified with first order structures and programs with sentences of certain logics such as first order logic, least fixpoint logic, or monadic second order logic.

Some of the oldest results of decriptive complexity theory are characterization results of known complexity classes, e.g., NP is equivalent to existential second order logic by Fagin and PTIME to least fixpoint logic by Immerman and Vardi. It is also known that there are quite tight correspondences between polynomial (resp. space) time bounds and quantifier ranks (resp. number of variables) of sentences. Most importantly, though, descriptive complexity provides a framework and methods, such as logical games, to study the complexity of specific problems.

I shall first survey some known results of the field, and then explain how generalized quantifiers fit into the picture. I shall then present as a case study a solution of the problem when the equicardinality quantifier is definable be means of a cardinality quantifier.