Absorbing subalgebra, cyclic terms and the constraint satisfaction problem

2012
journal article
article
dc.abstract.enThe 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 nearunanimity terms (proved by McKenzie and Mar´oti) in an elementary and self-contained way.en
dc.affiliationWydział Matematyki i Informatyki : Zespół Katedr i Zakładów Informatyki Matematycznejpl
dc.contributor.authorBarto, Liborpl
dc.contributor.authorKozik, Marcin - 129358 pl
dc.date.accessioned2014-08-01T14:24:44Z
dc.date.available2014-08-01T14:24:44Z
dc.date.issued2012pl
dc.date.openaccess0
dc.description.accesstimew momencie opublikowania
dc.description.number1pl
dc.description.versionostateczna wersja wydawcy
dc.description.volume8pl
dc.identifier.articleid7pl
dc.identifier.doi10.2168/LMCS-8(1:7)2012pl
dc.identifier.issn1860-5974pl
dc.identifier.projectROD UJ / Ppl
dc.identifier.urihttp://ruj.uj.edu.pl/xmlui/handle/item/436
dc.languageengpl
dc.language.containerengpl
dc.rightsUdzielam licencji. Uznanie autorstwa - Bez utworów zależnych 4.0 Międzynarodowa*
dc.rights.licenceCC-BY-ND
dc.rights.urihttp://creativecommons.org/licenses/by-nd/4.0/legalcode.pl*
dc.share.typeotwarte czasopismo
dc.subtypeArticlepl
dc.titleAbsorbing subalgebra, cyclic terms and the constraint satisfaction problempl
dc.title.journalLogical Methods in Computer Sciencepl
dc.typeJournalArticlepl
dspace.entity.typePublication
Affiliations

* The migration of download and view statistics prior to the date of April 8, 2024 is in progress.

Views
0
Views per month