velikost textu

Constraint Satisfaction Problem and Universal Algebra

Upozornění: Informace získané z popisných dat či souborů uložených v Repozitáři závěrečných prací nemohou být použity k výdělečným účelům nebo vydávány za studijní, vědeckou nebo jinou tvůrčí činnost jiné osoby než autora.
Název:
Constraint Satisfaction Problem and Universal Algebra
Název v češtině:
Problém splnitelnosti omezení a univerzální algebra
Typ:
Disertační práce
Autor:
RNDr. Alexandr Kazda, Ph.D.
Školitel:
Mgr. Libor Barto, Ph.D.
Oponenti:
Mgr. Pavel Růžička, Ph.D.
Prof. Matt Valeriote
Id práce:
76171
Fakulta:
Matematicko-fyzikální fakulta (MFF)
Pracoviště:
Katedra algebry (32-KA)
Program studia:
Matematika (P1101)
Obor studia:
Algebra, teorie čísel a matematická logika (4M1)
Přidělovaný titul:
Ph.D.
Datum obhajoby:
20. 6. 2013
Výsledek obhajoby:
Prospěl/a
Jazyk práce:
Angličtina
Klíčová slova:
CSP, univerzální algebra, orientovaný graf, absorpce
Klíčová slova v angličtině:
CSP, universal algebra, digraph, absorption
Abstrakt:
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
Abstract v angličtině:
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
Dokumenty
Stáhnout Dokument Autor Typ Velikost
Stáhnout Text práce RNDr. Alexandr Kazda, Ph.D. 649 kB
Stáhnout Abstrakt v českém jazyce RNDr. Alexandr Kazda, Ph.D. 25 kB
Stáhnout Abstrakt anglicky RNDr. Alexandr Kazda, Ph.D. 25 kB
Stáhnout Posudek vedoucího Mgr. Libor Barto, Ph.D. 52 kB
Stáhnout Posudek oponenta Mgr. Pavel Růžička, Ph.D. 49 kB
Stáhnout Posudek oponenta Prof. Matt Valeriote 75 kB
Stáhnout Záznam o průběhu obhajoby prof. RNDr. Jan Krajíček, DrSc. 58 kB
Stáhnout Errata RNDr. Alexandr Kazda, Ph.D. 109 kB