Personal tools
You are here: Home Events LFCS Seminars-Folder LFCS Seminar: Barnaby Martin

LFCS Seminar: Barnaby Martin

— filed under:

A tetrachotomy for positive equality-free logic

  • LFCS Seminar
When Sep 11, 2012
from 04:00 PM to 05:00 PM
Where IF 2.33 (TBC)
Add event to calendar vCal

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.

Document Actions