Expressibility and tractability

This thesis is composed of three separate, yet related strands. They have in common the notion that computational problems are regarded not as sets of strings, but as classes of finite structures. Our "computing devices", be they of a logical, traditionally computational, or algebraic nature, all work directly upon such structures. This is in contrast to traditional computability and complexity theory, where machines act instead upon some encoding of structures.;We begin by investigating a restriction of the question of whether or not NP = co-NP. In particular, we consider the effect of adding a transitive closure operator to monadic NP, and show that the resulting logic is a strict extension of it which is not closed under complementation. This extends Fagin's result that monadic NP is itself not closed under complementation.;We then investigate the expressive power of a class of program schemes which we call RFDPS. We prove a strong result limiting the expressive power of this class, and use it to obtain a strict, infinite hierarchy of problem classes within RFDPS. To our knowledge, this is the first strict, infinite hierarchy in a polynomial-time logic which properly extends inductive fixed-point logic (with the property that the union of the classes of the hierarchy consists of the class of problems definable in the polynomial-time logic itself).;Finally, we turn our attention to constraint satisfaction problems. This important class of problems is NP-hard in general, but many restrictions to it have been identified over the years which ensure its tractability. We introduce a method of combining two tractable classes over disjoint domains, so as to synthesise new tractable classes. We demonstrate that these new classes are genuinely novel, and extend naturally to yet further tractable classes. The algorithms for solving these extended classes can be less than obvious.