Complexity of Existential Positive First-Order Logic

International audienceLet Γ be a (not necessarily finite) structure with a finite relational signature. We prove that deciding whether a given existential positive sentence holds in Γ is in LOG SPACE or complete for the class CSP(Γ)NP under deterministic polynomial-time many-one reductions. Here, CSP(Γ)NP is the class of problems that can be reduced to the constraint satisfaction problem of Γ under non-deterministic polynomial-time many-one reductions