We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
Complexity of existential positive first-order logic.
- Authors
Bodirsky, Manuel; Hermann, Miki; Richoux, Florian
- Abstract
Let Γ 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 LogSpace 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.
- Subjects
FIRST-order logic; COMPUTATIONAL complexity; PREDICATE (Logic); TYPE theory; PROPOSITION (Logic); DETERMINISTIC algorithms; POLYNOMIAL time algorithms
- Publication
Journal of Logic & Computation, 2013, Vol 23, Issue 4, p753
- ISSN
0955-792X
- Publication type
Article
- DOI
10.1093/logcom/exr043