  Let gamma be a (not necessarily finite) structure with a finite relational
signature. We prove that deciding whether a given existential positive sentence
holds in gamma is in Logspace or complete for the class CSP(gamma)_NP under
deterministic polynomial-time many-one reductions. Here, CSP(gamma)_NP is the
class of problems that can be reduced to the Constraint Satisfaction Problem of
gamma under non-deterministic polynomial-time many-one reductions.
