Original title:
Homomorfismy do unárních algeber
Translated title:
Homomorphisms into unary algebras
Authors:
Škrobánek, Jiří ; Barto, Libor (advisor) ; Bulín, Jakub (referee) Document type: Bachelor's theses
Year:
2021
Language:
eng Abstract:
[eng][cze] This thesis studies the computational complexity of constraint satisfaction problem (CSP) over structures with unary operations (unary algebras). We concentrate on a special class of such CSPs, so called reversing problems. We present a new proof of complexity classification for reversing problems, which uses the algebraic approach based on studying polymorphisms. We show that some reversing problems admit near unanimity polymorphisms (and are therefore solvable in polynomial time) while the remaining reversing problems do not admit weak near unanimity polymorphisms (and are therefore NP-complete).Tato práce se zabývá výpočetní složitostí problému splnitelnosti omezení (CSP) nad strukturami s unárními operacemi (unárními algebrami). Zaměřujeme se na speciální třídu CSP, takzvané reverzní problémy. Představíme nový důkaz klasifikace složitosti reverzních problémů, jenž využije algebraického přístupu založeného na zkoumání polymorfismů. Ukážeme, že některé reverzní problémy připouštějí polymorfismus téměř úplné shody (a jsou tedy řešitelné v polynomiálním čase). Zato ostatní reverzní problémy nepřipouštějí polymorfismus slabé téměř úplné shody - WNU (a jsou tedy NP-úplné).
Keywords:
Constraint Satisfaction Problem|Weak Near Unanimity|Homomorphism|Reversing Problem; Problém splnitelnosti omezení (CSP)|Slabá téměř úplná shoda (WNU)|Homomorfismus|Reverzní problém
Institution: Charles University Faculties (theses)
(web)
Document availability information: Available in the Charles University Digital Repository. Original record: http://hdl.handle.net/20.500.11956/147688