Original title: Problém splnitelnosti omezení a univerzální algebra
Translated title: Constraint Satisfaction Problem and Universal Algebra
Authors: Kazda, Alexandr ; Barto, Libor (advisor) ; Růžička, Pavel (referee) ; Valeriote, Matt (referee)
Document type: Doctoral theses
Year: 2013
Language: eng
Abstract: [eng] [cze]
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 Práce sestává ze souboru mých příspěvků v oblasti univerzální algebry. Naší hlavní oblastí zájmu jsou algebry polymorfismů relačních struktur, motivací pak především složitost problému splnitelnosti omezení (CSP). Nejprve ukážeme pomocí univerzální algebry (a stopového množství analýzy), že CSP náhodné relační struktury je skoro jistě NP-úplný. Pokračujeme studiem orientovaných grafů, které mají Mal'cevův polymorfismus. Ukážeme, že takové grafy už nutně musí mít majoritu. Dále pak demonstrujeme použití techniky absorpce: Přinášíme nový důkaz faktu, že kongruenčně modulární reflexivní ori- entované grafy mají vždy NU polymorfismus. Na závěr práce prezentujeme alge- braický důkaz výsledku (poprvé dokázaného kombinatoriky), že 3-konzervativní relační struktury s nejvýše binárními relacemi se vyznačují jednoduchou dicho- tomií: Jejich CSP je bud' NP-úplné, nebo je lze řešit pomocí metody lokální konzistence. 1
Keywords: absorption; CSP; digraph; universal algebra; absorpce; CSP; orientovaný graf; univerzální algebra

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/53224

Permalink: http://www.nusl.cz/ntk/nusl-322524


The record appears in these collections:
Universities and colleges > Public universities > Charles University > Charles University Faculties (theses)
Academic theses (ETDs) > Doctoral theses