ECCC-Report TR09-111https://eccc.weizmann.ac.il/report/2009/111Comments and Revisions published for TR09-111en-usSat, 07 Nov 2009 23:34:14 +0200
Paper TR09-111
| Model-Theoretic Characterization of Complexity Classes |
Walid Gomaa
https://eccc.weizmann.ac.il/report/2009/111Model 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.Sat, 07 Nov 2009 23:34:14 +0200https://eccc.weizmann.ac.il/report/2009/111