[cevi]

This may only be tangentially related, but you might be interested in the recent research on Qualitative Constraint Satisfaction Problems - a good introduction to the topic is Manuel Bodirsky's habilitation thesis [1].

The purpose of the subject is, roughly speaking, to exhaustively characterize all types of reliable reasoning which can be carried out efficiently - some people say they are searching for "a logic for P". The techniques used are a mix of ideas from model theory, universal algebra, Ramsey theory, and computer science. Given the ridiculously ambitious scope of the project, I think the rate of progress (especially in the past few years) is astounding.

[1] https://arxiv.org/pdf/1201.0856.pdf