Distance Constraint Satisfaction Problems

Details Distance Constraint Satisfaction Problems Distance Constraint Satisfaction Problems

2010-04-22

arxiv.org/abs/1004.3842v2

Computer Science

Computational Complexity

21 pages, 2 figures

Scientific paper

We study the complexity of constraint satisfaction problems for templates Gamma that are first-order definable in (Z; succ), the integers with the successor relation. Assuming a widely believed conjecture from finite domain constraint satisfaction (we require the tractability conjecture by Bulatov, Jeavons and Krokhin in the special case of transitive finite templates), we provide a full classification for the case that Gamma is locally finite (i.e., the Gaifman graph of Gamma has finite degree). We show that one of the following is true: The structure Gamma is homomorphically equivalent to a structure with a certain majority polymorphism (which we call modular median) and CSP(Gamma) can be solved in polynomial time, or Gamma is homomorphically equivalent to a finite transitive structure, or CSP(Gamma) is NP-complete.

Affiliated with

Also associated with

No associations

Rating

Distance Constraint Satisfaction Problems 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 Distance Constraint Satisfaction Problems, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Distance Constraint Satisfaction Problems will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-458819