The Lattice Structure of Sets of Surjective Hyper-Operations

We study the lattice structure of sets (monoids) of surjective hyper-operations on an

n

-element domain. Through a Galois connection, these monoids form the algebraic counterparts to sets of relations closed under definability in positive first-order (fo) logic without equality. Specifically, for a countable set of relations (forming the finite-domain structure)

$\mathcal{B}$

, the set of relations definable over

$\mathcal{B}$

in positive fo logic without equality consists of exactly those relations that are invariant under the surjective hyper-endomorphisms (shes) of

$\mathcal{B}$

. The evaluation problem for this logic on a fixed finite structure is a close relative of the quantified constraint satisfaction problem (QCSP).

We study in particular an inverse operation that specifies an automorphism of our lattice. We use our results to give a dichotomy theorem for the evaluation problem of positive fo logic without equality on structures that are

she-complementative

, i.e. structures

$\mathcal{B}$

whose set of shes is closed under inverse. These problems turn out either to be in

L

or to be

Pspace

-complete.

We go on to apply our results to certain digraphs. We prove that the evaluation of positive fo without equality on a semicomplete digraph is always

Pspace

-complete. We go on to prove that this problem is

NP

-hard for any graph of diameter at least 3. Finally, we prove a tetrachotomy for antireflexive and reflexive graphs, modulo a known conjecture as to the complexity of the QCSP on connected non-bipartite graphs. Specifically, these problems are either in

L

,

NP

-complete,

co-NP

-complete or

Pspace

-complete.