The LSV seminar takes place on Tuesday at 11:00 AM. The usual location is the conference room at Pavillon des Jardins (venue). If you wish to be informed by e-mail about upcoming seminars, please contact Stéphane Le Roux and Matthias Fuegger.
The seminar is open to public and does not require any form of registration.
We consider the problem of evaluating positive equality-free sentences of FO on a fixed, finite relational structure B. This may be seen as a generalisation of the Quantified Constraint Satisfaction Problem (QCSP), itself a generalisation of the Constraint Satisfaction Problem (CSP). We argue that our generalisation is not totally arbitrary, and that ours is the only problem in a large class - other than the CSP and QCSP - whose complexity taxonomy was unsolved.
We introduce surjective hyper-endomorphisms in order to give a Galois connection that characterises definability in positive equality-free FO. Through the algebraic method we are able to characterise the complexity of our problem for all finite structures B. Specifically, the problem is either in Logspace, NP-complete, co-NP-complete or Pspace-complete.
The problem appears obtuse, but possesses a surprising elegance. There may yet be lessons to be learnt in the methodology of the solution of this case, for the continuing program for CSP.