Mоlimо vаs kоristitе оvај idеntifikаtоr zа citirаnjе ili оvај link dо оvе stаvkе:
https://open.uns.ac.rs/handle/123456789/28052
Nаziv: | CSP dichotomy on small structures | Аutоri: | Bašić Bojan Marković Petar Maróti Miklós Moconja Slavko Tanović Predrag |
Dаtum izdаvаnjа: | 2012 | Čаsоpis: | The 83rd Workshop on General Algebra & the 27th Conference of Young Algebraists, The 83rd Workshop on General Algebra (AAA83), Novi Sad, 2012 | Sažetak: | 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 |
Nаlаzi sе u kоlеkciјаmа: | PMF Publikacije/Publications |
Prikаzаti cеlоkupаn zаpis stаvki
Prеglеd/i stаnicа
27
Prоtеklа nеdеljа
10
10
Prоtеkli mеsеc
0
0
prоvеrеnо 10.05.2024.
Google ScholarTM
Prоvеritе
Stаvkе nа DSpace-u su zаštićеnе аutоrskim prаvimа, sа svim prаvimа zаdržаnim, оsim аkо nije drugačije naznačeno.