Forbidden lists (NP and CSP for combinatorialists)

Details Forbidden lists (NP and CSP for combinatorialists) Forbidden lists (NP and CSP for combinatorialists)

2007-06-12

arxiv.org/abs/0706.1704v1

Mathematics

Combinatorics

22 pages, 3 figures,

Scientific paper

We present a definition of the class NP in combinatorial context as the set of languages of structures defined by finitely many forbidden lifted substructures. We apply this to special syntactically defined subclasses and show how they correspond to naturally defined (and intensively studied) combinatorial problems. We show that some types of combinatorial problems like edge colorings and graph decompositions express the full computational power of the class NP. We then characterize Constraint Satisfaction Problems (i.e. H-coloring problems) which are expressible by finitely many forbidden lifted substructures. This greatly simplifies and generalizes the earlier attempts to characterize this problem. As a corollary of this approach we perhaps find a proper setting of Feder and Vardi analysis of CSP languages within the class MMSNP.

Affiliated with

Also associated with

No associations

Rating

Forbidden lists (NP and CSP for combinatorialists) 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 Forbidden lists (NP and CSP for combinatorialists), we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Forbidden lists (NP and CSP for combinatorialists) will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-359724