Using program schemes to capture polynomial-time logically on certain classes of structures

Stewart, I.A.

Abstract

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.

Citation

Stewart, I. (2003). Using program schemes to capture polynomial-time logically on certain classes of structures. LMS journal of computation and mathematics, 6, 40-67

• Journal Article Type: Article
• Publication Date: Mar 1, 2003
• Deposit Date: Jun 29, 2009
• Publicly Available Date: Aug 25, 2009
• Journal: LMS Journal of Computation and Mathematics
• Electronic ISSN: 1461-1570
• Publisher: Cambridge University Press
• Peer Reviewed: Peer Reviewed
• Volume: 6
• Pages: 40-67
• Keywords: Computational complexity. Descriptive complexity. Finite model theory.
• Public URL: https://durham-repository.worktribe.com/output/1627817
• Publisher URL: http://www.lms.ac.uk/jcm/6/lms2002-004/