The complexity of positive first-order logic without equality II: the four-element case

We study the complexity of evaluating positive equality-free sentences of first-order logic over fixed, finite structures B . This may be seen as a natural generalisation of the non-uniform quantified constraint satisfaction problem QCSP (B) . Extending the algebraic methods of a previous paper, we derive a complete complexity classification for these problems as B ranges over structures of domain size 4. Specifically, each problem is either in L, is NP-complete, is co-NP-complete or is Pspace-complete.