Název: Homomorfismy do unárních algeber
Překlad názvu: Homomorphisms into unary algebras
Autoři: Škrobánek, Jiří ; Barto, Libor (vedoucí práce) ; Bulín, Jakub (oponent)
Typ dokumentu: Bakalářské práce
Rok: 2021
Jazyk: eng
Abstrakt: [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é).
Klíčová slova: Problém splnitelnosti omezení (CSP)|Slabá téměř úplná shoda (WNU)|Homomorfismus|Reverzní problém; Constraint Satisfaction Problem|Weak Near Unanimity|Homomorphism|Reversing Problem

Instituce: Fakulty UK (VŠKP) (web)
Informace o dostupnosti dokumentu: Dostupné v digitálním repozitáři UK.
Původní záznam: http://hdl.handle.net/20.500.11956/147688

Trvalý odkaz NUŠL: http://www.nusl.cz/ntk/nusl-451094


Záznam je zařazen do těchto sbírek:
Školství > Veřejné vysoké školy > Univerzita Karlova > Fakulty UK (VŠKP)
Vysokoškolské kvalifikační práce > Bakalářské práce