Complexity Theoretic Model Theory and Algebra
Douglas Cenzer · 2013
In this paper we will survey some recent results on complexity theoretic model theory and algebra Essentially there are two major themes in this work The rst which we call complexity theoretic model theory deals with model ex istence questions For example given a recursive model A is there there a polynomial time exponential time polynomial space etc model B which is isomorphic to A The second theme which we call complexity theoretic al gebra xes a given polynomial time structure and explores the properties of that structure For example we can ask whether every polynomial time ideal of a given polynomial time representation of the free Boolean algebra can be extended to a maximal polynomial time ideal In both cases one uses the rich theory of recursive model theory and algebra as a reference but looks at resource bounded versions of the results in those areas It turns out that not only are there a number of contrasts between results in recursive model theory and algebra and complexity theoretic model theory and algebra but some new and interesting phenomena occur in the study of complexity theoretic model theory and algebra That is there are results in recursive model theory and algebra for which the natural complexity theoretic analogue is true but requires a more delicate proof which incorporates the re source bounds There are also results in recursive model theory and algebra for