On the tractability of some minions below AT.

licenciate
dc.abstract.enSince Promise CSP was introduced a few years ago by Brakensiek and Guruswami, there has been an active research aimed at establishing complexity classification for PCSPs, in particular Boolean PCSPs, based on algebraic approach to PCSP. One result in this area is dichotomy of symmetric Boolean PCSPs. The authors identified a "new" polymorphism (Alternating-Threshold polymorphism) that allows for polynomial-time algorithm, which hasn't appeared in CSP context. In this thesis, we are attempting to establish dichotomy for the family of subminions of minion AT generated by Alternating-Polymorphisms of all arities. To be more specific, we focus on minion ST identified by Szymon Stankiewicz. We first show that one of the most powerful tools to prove hardness cannot be applied to ST, and then provide a finite PCSP template that defines ST.pl
dc.abstract.plOd momentu wprowadzenia Promise CSP kilka lat temu przez Brakensieka i Guruswamiego, prowadzone są aktywne badania, mające na celu ustalenia klasyfikacji złożonościowej dla PCSP, zwłaszcza dla Boolowskich PCSP, oparte na podejściu algebraicznym. Jednym z wyników w tym obszarze jest dowód dychotomii dla symetrycznych Boolowskich PCSP. Autorzy zidentyfikowali "nowy" polimorfizm (Alternating-Threshold), który pozwala na wielomianowy algorytm, i który nie pojawiał się w kontekście CSP. W tej pracy, próbujemy ustalić dychotomię dla rodziny podminionów miniona AT zgenerowanego przez Alternating-Threshold polimorfizmy wszystkich arności. Mówiąc dokładniej, skupiamy się na minionie ST zidentyfikowanym przez Szymona Stankiewicza. Najpierw pokazujemy, że jednego z najpotężniejszych narzędzi do pokazywania trudności nie można zastosować do ST, a następnie rozważamy skończony szablon PCSP, który definiuje ST.pl
dc.affiliationWydział Matematyki i Informatykipl
dc.areaobszar nauk ścisłychpl
dc.contributor.advisorKozik, Marcin - 129358 pl
dc.contributor.authorBanakh, Demianpl
dc.contributor.departmentbycodeUJK/WMI2pl
dc.contributor.reviewerKozik, Marcin - 129358 pl
dc.contributor.reviewerWrona, Michałpl
dc.date.accessioned2023-03-16T22:30:39Z
dc.date.available2023-03-16T22:30:39Z
dc.date.submitted2021-07-09pl
dc.fieldofstudyinformatyka analitycznapl
dc.identifier.apddiploma-150232-265381pl
dc.identifier.urihttps://ruj.uj.edu.pl/xmlui/handle/item/309208
dc.languageengpl
dc.subject.enconstraint satisfaction, CSP, PCSP, algebraic approach, universal algebra, computational complexitypl
dc.subject.plspełnianie więzów, CSP, PCSP, podejście algebraiczne, algebra uniwersalna, złożoność obliczeniowapl
dc.titleOn the tractability of some minions below AT.pl
dc.title.alternativeZłożoność obliczeniowa dla niektórych minionów poniżej AT.pl
dc.typelicenciatepl
dspace.entity.typePublication
dc.abstract.enpl
Since Promise CSP was introduced a few years ago by Brakensiek and Guruswami, there has been an active research aimed at establishing complexity classification for PCSPs, in particular Boolean PCSPs, based on algebraic approach to PCSP. One result in this area is dichotomy of symmetric Boolean PCSPs. The authors identified a "new" polymorphism (Alternating-Threshold polymorphism) that allows for polynomial-time algorithm, which hasn't appeared in CSP context. In this thesis, we are attempting to establish dichotomy for the family of subminions of minion AT generated by Alternating-Polymorphisms of all arities. To be more specific, we focus on minion ST identified by Szymon Stankiewicz. We first show that one of the most powerful tools to prove hardness cannot be applied to ST, and then provide a finite PCSP template that defines ST.
dc.abstract.plpl
Od momentu wprowadzenia Promise CSP kilka lat temu przez Brakensieka i Guruswamiego, prowadzone są aktywne badania, mające na celu ustalenia klasyfikacji złożonościowej dla PCSP, zwłaszcza dla Boolowskich PCSP, oparte na podejściu algebraicznym. Jednym z wyników w tym obszarze jest dowód dychotomii dla symetrycznych Boolowskich PCSP. Autorzy zidentyfikowali "nowy" polimorfizm (Alternating-Threshold), który pozwala na wielomianowy algorytm, i który nie pojawiał się w kontekście CSP. W tej pracy, próbujemy ustalić dychotomię dla rodziny podminionów miniona AT zgenerowanego przez Alternating-Threshold polimorfizmy wszystkich arności. Mówiąc dokładniej, skupiamy się na minionie ST zidentyfikowanym przez Szymona Stankiewicza. Najpierw pokazujemy, że jednego z najpotężniejszych narzędzi do pokazywania trudności nie można zastosować do ST, a następnie rozważamy skończony szablon PCSP, który definiuje ST.
dc.affiliationpl
Wydział Matematyki i Informatyki
dc.areapl
obszar nauk ścisłych
dc.contributor.advisorpl
Kozik, Marcin - 129358
dc.contributor.authorpl
Banakh, Demian
dc.contributor.departmentbycodepl
UJK/WMI2
dc.contributor.reviewerpl
Kozik, Marcin - 129358
dc.contributor.reviewerpl
Wrona, Michał
dc.date.accessioned
2023-03-16T22:30:39Z
dc.date.available
2023-03-16T22:30:39Z
dc.date.submittedpl
2021-07-09
dc.fieldofstudypl
informatyka analityczna
dc.identifier.apdpl
diploma-150232-265381
dc.identifier.uri
https://ruj.uj.edu.pl/xmlui/handle/item/309208
dc.languagepl
eng
dc.subject.enpl
constraint satisfaction, CSP, PCSP, algebraic approach, universal algebra, computational complexity
dc.subject.plpl
spełnianie więzów, CSP, PCSP, podejście algebraiczne, algebra uniwersalna, złożoność obliczeniowa
dc.titlepl
On the tractability of some minions below AT.
dc.title.alternativepl
Złożoność obliczeniowa dla niektórych minionów poniżej AT.
dc.typepl
licenciate
dspace.entity.type
Publication
Affiliations

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

Views
3
Views per month
Views per city
Krakow
1

No access

No Thumbnail Available