Polynomial Interpretation Logic on ω-Categorical Structures

In the search of a way to describe all polynomial-time decision algorithms, there have been many iterations of logical systems. One of the best candidates, Choiceless Polynomial Time (CPT), has been shown to have equivalent expressive power to a less complex Polynomial Interpretation Logic (PIL). The new methodology in PIL is more suitable for constraint satisfaction problems (CSPs), a set of decision problems of interest to many research areas. In this thesis we demonstrate the connection between the run of a PIL program on a structure eq A and A . This connection yields a formula in the original language of the structure equivalent to the output of the program. Under the condition that the structure is a model-complete core, we eq find PIL programs to be polynomial-time equivalent to a CSP. We also show some properties of A which further suggest the usefulness of CSPs in formulating and constructing algorithms for more general decision problems on special classes of infinite structures. We end by showing we can use PIL programs to express the solvability of Cyclic Equation Systems over different domains.