Libor Barto ; Marcin Kozik - Absorbing Subalgebras, Cyclic Terms, and the Constraint Satisfaction Problem

lmcs:673 - Logical Methods in Computer Science, February 20, 2012, Volume 8, Issue 1 -
Absorbing Subalgebras, Cyclic Terms, and the Constraint Satisfaction Problem

Authors: Libor Barto ; Marcin Kozik

    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óti) in an elementary and self-contained way.

    Volume: Volume 8, Issue 1
    Published on: February 20, 2012
    Accepted on: June 25, 2015
    Submitted on: December 30, 2010
    Keywords: Computer Science - Logic in Computer Science,F.2.2, F.4.1

    Linked data

    Source : ScholeXplorer IsCitedBy ARXIV 2102.07531
    Source : ScholeXplorer IsCitedBy DOI 10.4230/lipics.icalp.2021.138
    Source : ScholeXplorer IsCitedBy DOI 10.48550/arxiv.2102.07531
    Source : ScholeXplorer IsCitedBy HANDLE 11420/12070
    • 10.48550/arxiv.2102.07531
    • 10.4230/lipics.icalp.2021.138
    • 2102.07531
    • 11420/12070
    Smooth Approximations and Relational Width Collapses
    Mottet, Antoine ; Nagy, Tomáš ; Pinsker, Michael ; Wrona, Michał ;

    51 Documents citing this article


    Consultation statistics

    This page has been seen 464 times.
    This article's PDF has been downloaded 235 times.