This research is a logical approach to the study of computational complexity. This approach will enlist one of the main traditions which has emerged in mathematical logic since the 1930's namely, model theory. Model theory studies the relation between logical languages and their interpretations and has developed powerful techniques to answer questions about the expressive power of a variety of logical languages.
A significant feature of this work is that it forgoes, to a large extent, the use of machine models of computation in the study of complexity. Much valuable work in complexity theory has involved careful analysis of the resource requirements of various algorithms on specified abstract machines. It may be possible to obtain new insights into the complexity of combinatorial problems by analyzing these problems in machine-independent, logical terms. Some of the problems that will be considered, such as the separation of fixed-point definability from first-order definability over certain classes of graphs, have direct implications for the separation of complexity classes. Though these implications are certainly significant, the focus of this research is to achieve a deeper understanding of the problems themselves by the use of logical techniques.
In addition to offering a machine-independent approach to the study of the complexity of combinatorial problems, logic deals directly with questions concerning representing and reasoning about information. Such questions are of evident significance across the breadth of computer science. This work will bear on some such questions, particularly as they arise within the context of database theory.
