Algebraické metody pro CSP
Cílem této diplomové práce je představení pokročilých metod univerzální algebry sloužících ke klasifikaci složitosti problémů s omezujícími podmínkami. Zejména se zajímáme o teorii krotkých kongruencí (TCT). Kromě úvodu do této teorie je v práci ukázáno, jak lze TCT využít k rozhodnutí, zda je nějak...
Uloženo v:
| Hlavní autor: | |
|---|---|
| Další autoři: | |
| Typ dokumentu: | VŠ práce nebo rukopis |
| Jazyk: | Čeština |
| Vydáno: |
2010
|
| Témata: | |
| On-line přístup: | http://is.muni.cz/th/172743/prif_m/ |
| Shrnutí: | Cílem této diplomové práce je představení pokročilých metod univerzální algebry sloužících ke klasifikaci složitosti problémů s omezujícími podmínkami. Zejména se zajímáme o teorii krotkých kongruencí (TCT). Kromě úvodu do této teorie je v práci ukázáno, jak lze TCT využít k rozhodnutí, zda je nějaký problém s omezujícími podmínkami rozhodnutelný v polynomiálním čase, nebo NP-úplný. V závěru práce je teorie aplikována na speciální (avšak významný) případ těchto problémů - řešitelnost soustav rovnic nad jistými konečnými pologrupami. The aim of this diploma thesis is to introduce the reader into some advanced methods of universal algebra. These methods - especially the tame congruence theory (TCT) - can be used to classify the complexity of constraint satisfaction problems (CSP's). The most important (and yet unresolved) question is whether every CSP is either decidable in polynomial time or NP-complete. The thesis shows how it is possible to apply the TCT in order to advance our knowledge in this area. The final chapter presents the TCT-related methods applied in special (but important) case - solving of systems of equations over certain finite semigroups. |
|---|---|
| Popis jednotky: | Vedoucí práce: Ondřej Klíma |
| Fyzický popis: | 92 l. |