Please use this identifier to cite or link to this item:
https://open.uns.ac.rs/handle/123456789/28052
Title: | CSP dichotomy on small structures | Authors: | Bašić Bojan Marković Petar Maróti Miklós Moconja Slavko Tanović Predrag |
Issue Date: | 2012 | Journal: | The 83rd Workshop on General Algebra & the 27th Conference of Young Algebraists, The 83rd Workshop on General Algebra (AAA83), Novi Sad, 2012 | Abstract: | Given a finite relational structure (template), the fixed-template Constraint Satisfaction Problem asks whether there exists a homomorphism from a similar finite relational structure (which is the input of the problem) into the template. Dichotomy Conjecture about complexity of the Constraint Satisfaction Problem states that each fixed-template Constraint Satisfaction Problem is either tractable or NP-complete (depending on which template is fixed). We review the recent results on the CSP Dichotomy Conjecture which attempt to solve it in small cases. The highlight of our lecture is the result that the Dichotomy Conjecture holds for all templates having at most four elements, but we will also briefly review other recent results on small templates, as well as another application of the main technique used in our proof. | URI: | https://open.uns.ac.rs/handle/123456789/28052 |
Appears in Collections: | PMF Publikacije/Publications |
Show full item record
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.