Absorbing Subalgebras, Cyclic Terms, and the Constraint Satisfaction Problem

Details Absorbing Subalgebras, Cyclic Terms, and the Constraint Satisfaction Problem Absorbing Subalgebras, Cyclic Terms, and the Constraint Satisfaction Problem

2012-01-03

arxiv.org/abs/1201.0557v3

LMCS 8 (1:7) 2012

Computer Science

Logic in Computer Science

Scientific paper

10.2168/LMCS-8(1:7)2012

The Algebraic Dichotomy Conjecture states that the Constraint Satisfaction Problem over a fixed template is solvable in polynomial time if the algebra of polymorphisms associated to the template lies in a Taylor variety, and is NP-complete otherwise. This paper provides two new characterizations of finitely generated Taylor varieties. The first characterization is using absorbing subalgebras and the second one cyclic terms. These new conditions allow us to reprove the conjecture of Bang-Jensen and Hell (proved by the authors) and the characterization of locally finite Taylor varieties using weak near-unanimity terms (proved by McKenzie and Mar\'oti) in an elementary and self-contained way.

Affiliated with

Also associated with

No associations

Rating

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

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-183451