complexity theory

The question of whether there is a logic that characterises polynomial-time is arguably the most important open question in finite model theory. The study of extensions of fixed-point logic are of central importance to this question. It was shown by …

Fixed-point logic with rank (FPR) is an extension of fixed-point logic with counting (FPC) with operators for computing the rank of a matrix over a finite field. The expressive power of FPR properly extends that of FPC and is contained in PTime, but …