Home » Subject » Logic » Finite Model Theory

Fixed-point logic with counting

Importance: Medium ✭✭
Author(s): Blass, Andreas
Subject: Logic
» Finite Model Theory
Keywords: Capturing PTime
counting quantifiers
Fixed-point logic
FMT03-Bedlewo
Recomm. for undergrads: no
Posted by: dberwanger
on: May 18th, 2012
Question   Can either of the following be expressed in fixed-point logic plus counting:
    \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?

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].

Bibliography

[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.
add new comment