The problem concerns the extension of Monadic Second Order Logic (over a binary relation representing the edge relation) with the following atomic formulas:
where is a fixed recursive set of integers.
Let us fix and a closed formula in this language.
- Given a graph, does it have a perfect matching, i.e., a set of edges such that every vertex is incident to exactly one edge from ?
- Given a square matrix over a finite field (regarded as a structure in the natural way, as described in [BGS02]), what is its determinant?