The thesis consists of a collection of my contributions to universal algebra. Motivated by the Constraint Satisfaction Problem (CSP), we study the algebras of polymorphisms of relational structures. We begin by showing by an algebraic argument (and a bit of calculus) that random relational structures' CSP is almost always NP-complete. We then study digraphs with a Maltsev polymorphism, and conclude that such digraphs must also have a majority polymorphism. Next, we show how to use absorption tech- niques to prove that congruence modular reflexive digraphs must have an NU operation. We close our work by giving an algebraic proof of a result (first obtained by graph theorists) that 3-conservative relational structures with only unary and binary relations either define NP-complete CSP, or CSP for them can be solved by the local consistency algorithm. 1
| Identifer | oai:union.ndltd.org:nusl.cz/oai:invenio.nusl.cz:322524 |
| Date | January 2013 |
| Creators | Kazda, Alexandr |
| Contributors | Barto, Libor, Růžička, Pavel, Valeriote, Matt |
| Source Sets | Czech ETDs |
| Language | English |
| Detected Language | English |
| Type | info:eu-repo/semantics/doctoralThesis |
| Rights | info:eu-repo/semantics/restrictedAccess |
Page generated in 0.0018 seconds