Please use this identifier to cite or link to this item:
https://open.uns.ac.rs/handle/123456789/28052
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Bašić Bojan | - |
dc.contributor.author | Marković Petar | - |
dc.contributor.author | Maróti Miklós | - |
dc.contributor.author | Moconja Slavko | - |
dc.contributor.author | Tanović Predrag | - |
dc.date.accessioned | 2020-12-13T22:46:48Z | - |
dc.date.available | 2020-12-13T22:46:48Z | - |
dc.date.issued | 2012 | - |
dc.identifier.uri | https://open.uns.ac.rs/handle/123456789/28052 | - |
dc.description.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. | en |
dc.language.iso | en | - |
dc.relation.ispartof | The 83rd Workshop on General Algebra & the 27th Conference of Young Algebraists, The 83rd Workshop on General Algebra (AAA83), Novi Sad, 2012 | en |
dc.source | CRIS UNS | - |
dc.source.uri | http://cris.uns.ac.rs | - |
dc.title | CSP dichotomy on small structures | en |
dc.type | Conference Paper | en |
dc.identifier.url | https://www.cris.uns.ac.rs/record.jsf?recordId=82007&source=BEOPEN&language=en | en |
dc.relation.lastpage | 38 | - |
dc.relation.firstpage | 38 | - |
dc.identifier.externalcrisreference | (BISIS)82007 | - |
item.grantfulltext | none | - |
item.fulltext | No Fulltext | - |
crisitem.author.dept | Prirodno-matematički fakultet, Departman za matematiku i informatiku | - |
crisitem.author.dept | Prirodno-matematički fakultet, Departman za matematiku i informatiku | - |
crisitem.author.orcid | 0000-0002-1607-7139 | - |
crisitem.author.parentorg | Prirodno-matematički fakultet | - |
crisitem.author.parentorg | Prirodno-matematički fakultet | - |
Appears in Collections: | PMF Publikacije/Publications |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.