Constraints, MMSNP and expander relational structures

Details Constraints, MMSNP and expander relational structures Constraints, MMSNP and expander relational structures

2007-06-12

arxiv.org/abs/0706.1701v1

Mathematics

Combinatorics

15 pages, 1 figure, submitted to Combinatorica

Scientific paper

We introduce a concept of expander relations. We give a polynomial time construction for expander relational structures with large girth and constant degree. Our main tool is a new type of product for relational structures, the twisted product. We use these tools in the investigation of the complexity class of Constraint Satisfaction Problems (CSP), a generalization of (hyper)graph coloring problems and the class MMSNP introduced by Feder and Vardi. We prove that every CSP problem is computationally equivalent to the restriction of the same CSP problem to large girth structures. This implies that the classes CSP and MMSNP have the same computational power.

Affiliated with

Also associated with

No associations

Rating

Constraints, MMSNP and expander relational structures 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 Constraints, MMSNP and expander relational structures, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Constraints, MMSNP and expander relational structures will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-359695