Descriptive Complexity Theory and Programming Language Design

This node contains slides of a 1995 talk. Much of the content of the slides is also given in my course notes on inference rules. However these slides contain more examples and some additional results. In particular the characterizations of coNP, PSPACE, and EXPTIME appear only in these slides. These characterizations are unusual in that they associate well known features of logic programming with complexity classes. First we get a characterization of P by adding the restriction that every term in the head of a rules must appear in the body (this is not a standard feature). Then we get a characteriazation of coNP by intrucing disjunction (a well known feature). We get a characterization of PSPACE by adding negation by failure (another well known feature) and a characterization of EXPTIME by adding second order constructs (a less well known feature).

postscript