Complexity of Existential Positive First-Order Logic

Details Complexity of Existential Positive First-Order Logic Complexity of Existential Positive First-Order Logic

2010-11-22

arxiv.org/abs/1011.4757v2

Computer Science

Computational Complexity

8 pages

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Complexity of Existential Positive First-Order Logic does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Complexity of Existential Positive First-Order Logic, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Complexity of Existential Positive First-Order Logic will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-657141