__
TR09-111 | 5th November 2009 15:49
__

#### Model-Theoretic Characterization of Complexity Classes

**Abstract:**
Model theory is a branch of mathematical logic that investigates the

logical properties of mathematical structures. It has been quite

successfully applied to computational complexity resulting in an

area of research called descriptive complexity theory. Descriptive

complexity is essentially a syntactical characterization of

complexity classes using logical formalisms. However, there are still

much more of model theory technologies that have not yet been explored by

complexity theorists, especially the subarea of

classification/stability theory. This paper is divided into two

parts. The first part quickly surveys the main results of

descriptive complexity theory. In the second part we introduce the

field of classification/stability theory, then give the outlines of

a research project whose aim is to apply this theory to give a

semantical characterization of complexity classes. This would

initiate a brand new research area.