Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR09-111 | 5th November 2009 15:49

Model-Theoretic Characterization of Complexity Classes


Authors: Walid Gomaa
Publication: 7th November 2009 23:34
Downloads: 1799


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.

ISSN 1433-8092 | Imprint