CSP over oriented trees
| Thesis title in Czech: | CSP nad orientovanými stromy |
|---|---|
| Thesis title in English: | CSP over oriented trees |
| Key words: | CSP, orientované stromy, NP-úplnost |
| English key words: | CSP, oriented trees, NP-completeness |
| Academic year of topic announcement: | 2018/2019 |
| Thesis type: | Bachelor's thesis |
| Thesis language: | angličtina |
| Department: | Department of Algebra (32-KA) |
| Supervisor: | RNDr. Jakub Bulín, Ph.D. |
| Author: | hidden - assigned and confirmed by the Study Dept. |
| Date of registration: | 14.11.2018 |
| Date of assignment: | 14.11.2018 |
| Confirmed by Study dept. on: | 22.11.2018 |
| Date and time of defence: | 21.06.2019 08:00 |
| Date of electronic submission: | 09.05.2019 |
| Date of submission of printed version: | 17.05.2019 |
| Date of proceeded defence: | 21.06.2019 |
| Opponents: | doc. Mgr. Libor Barto, Ph.D. |
| Guidelines |
| Práce se zaměří na studium výpočetní složitosti problému splnitelnosti omezujících podmínek (CSP) nad orientovanými stromy,
konkrétněji na otázku, jaký je nejmenší orientovaný strom, jehož CSP je NP-úplný problém. |
| References |
| [1] T. Feder, M. Vardi: The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory, SIAM J. Comput., 28/1 (1998), 57–104.
[2] L. Barto, M. Kozik, M. Maroti, T. Niven: CSP dichotomy for special triads, Proc. Amer. Math. Soc. 137/9 (2009), 2921-2934 [3] L. Barto, J. Bulín: CSP dichotomy for special polyads with L. Barto, Int. J. Algebra Comput. 23/05 (2013), 1151–1174 |
| Preliminary scope of work |
| V článku [2] je zkonstruován příklad orientovaného stromu s 39 vrcholy, jehož CSP je NP-úplný problém. Jde o nejmenší takový orientovaný strom?
I když se problém týká výpočetní složitosti, žádné znalosti z teoretické informatiky nejsou potřeba, protože lze problém redukovat na studium operací kompatibilních s orientovanými stromy. Položená otázka je pravděpodobně příliš těžká. Student/ka se může pokusit pro nějaká n ručně ukázat, že všechny menší stromy mají polynomiálně řešitelné CSP, a pro nějaká větší n dokázat totéž za pomoci počítače. Další možností je zaměřit se jen na nějaké speciální třídy stromů, apod. |