Fixed-point logic with counting

Recomm. for undergrads: no
Posted by: dberwanger
on: May 18th, 2012

\begin{question} Can either of the following be expressed in fixed-point logic plus counting: \begin{enumerate} \item Given a graph, does it have a perfect matching, i.e., a set $M$ of edges such that every vertex is incident to exactly one edge from $M$? \item Given a square matrix over a finite field (regarded as a structure in the natural way, as described in [BGS02]), what is its determinant? \end{enumerate} \end{question}

It is known that (1) is expressible if restricted to bipartite graphs and that (2) is expressible if the field has only two elements. Both these results are in [BGS02].


[BGS02] A. Blass, Y. Gurevich, and S. Shelah, On polynomial time computation over unordered structures, J. Symbolic Logic 67 (2002) 1093--1125.

* indicates original appearance(s) of problem.