Publication details for Professor Iain StewartStewart, I.A. (2003). Using program schemes to capture polynomial-time logically on certain classes of structures. London Mathematical Society Journal of Computation and Mathematics 6: 40-67.
- Publication type: Journal Article
- ISSN/ISBN: 1461-1570
- Keywords: Computational complexity. Descriptive complexity. Finite model theory.
- Further publication details on publisher web site
- Durham Research Online (DRO) - may include full text
Author(s) from Durham
We continue the study of the expressive power of certain classes of program schemes on finite structures, in relation to more mainstream logics studied in finite model theory and to computational complexity. We show that there exists a program scheme, whose constructs are assignments and while-loops with quantifier-free tests and which has access to a stack, that can accept a P-complete problem, the deterministic path system problem, even in the absence of non-determinism so long as problem instances are presented in a functional style. (Our proof leans heavily on Cook's proof that the classes of formal languages accepted by deterministic and non-deterministic logspace auxiliary pushdown machines coincide). However, whilst our result is of independent interest, as it leads to a deterministic model of computation capturing P whose non-deterministic variant also captures P, we then show how our constructed program scheme can be used to build a successor relation in certain classes of structures, namely: the class of strongly-connected locally-ordered digraphs; the class of connected planar embeddings; and the class of triangulations, with the consequence that on these classes of graphs, (a fragment of) path system logic (with no built-in relations) captures exactly the polynomial-time solvable problems.