|
|
Promises in Satisfaction Problems
Asimi, Kristina ; Barto, Libor (vedoucí práce) ; Barnaby, Martin (oponent) ; Živný, Stanislav (oponent)
Short Abstract This thesis focuses on the complexity of the promise version of Constraint Satisfaction Problem (CSP) and its variants. The first study concerns the Promise Constraint Satisfaction Problem (PCSP), which extends the traditional CSP to include approximation variants of satisfiability and graph coloring. A specific PCSP, referred to as finding a valid Not-All-Equal solution to a 1-in- 3-SAT instance, has been shown by Barto [LICS '19] to lack finite tractability. While it can be reduced to a tractable CSP, the latter is necessarily over an infinite domain (unless P=NP). We say that such a PCSP is not finitely tractable and we initiate a systematic study of this phenomenon by giving a general necessary condition for finite tractability. Additionally, we characterize finite tractability within a class of templates. In the second study, we focus on the CSP in the context of first-order logic. The fixed-template CSP can be seen as the problem of deciding whether a given primitive positive first-order sentence is true in a fixed structure (also called model). We study a class of problems that generalizes the CSP simultaneously in two directions: we fix a set L of quantifiers and Boolean connectives, and we specify two versions of each constraint, one strong and one weak (making the promise version)....
|
|
|
Minion Cores of Clones
Kapytka, Maryia ; Barto, Libor (vedoucí práce) ; Zhuk, Dmitrii (oponent)
Tato práce poskytuje klasifikaci minionových homomorfismu a minonových jáder v rámci třídy vícesortových booleovských klonů. Tyto klony lze popsat jako klony definované na množině {0, 1}k = {0, 1} × {0, 1} × · · · × {0, 1}, kde klonové operace působí po složkách na k-ticích, které jsou určeny vícesortovými unárními nebo binárními relacemi. Druhá kapitola této práce se zaměřuje na prezentaci klíčových výsledků. Zavádíme určitá minionová jádra a stanovujeme jejich uspořádání. Dále dokazu- jeme, že každý klon výše uvedeného typu je ekvivalentní jednomu z těchto min- ionových jader.
|
|
|
Symmetric terms
Boroš, Martin ; Barto, Libor (vedoucí práce) ; Kompatscher, Michael (oponent)
V této práci studujeme symetrické relace a symetrické afinní podprostory Z ([n] k ) p . Práce je rozdělena na tři části. V první části poskytneme základní definice a fakta která jsou potřeba ve zbytku práce. V druhé části studujeme symetrické afinní podprostory Z ([n] k ) p . Dokážeme úplnou charakterizaci symetrických vektorových podprostorů v případě k = 2. Pomocí tohoto výsledku podáme charakterizaci toho, kdy každý symetrický afinní podprostor obsahuje konstantu pro k = 2. Ve třetí části studujeme symetrické relace algebry. Dokážeme, že za určitých předpokladů má algebra k-WNU termovou operaci. 1
|
|
|
Minimální Taylorovy klony na třech prvcích
Jankovec, Filip ; Barto, Libor (vedoucí práce)
Brady klasifikoval všechny minimální Taylorovy algebry na tří prvkové množině až na termovou ekvivalenci a izomorfismus, celkem takových algeber je 24. Práce zkoumá klony těchto algeber. Pro 12 z nich, práce charakterizuje operace v klonu a také uvádí relační popis klonu. 1
|
|
|
Barvení grafu a formální gramatiky
Elichová, Sára ; Holub, Štěpán (vedoucí práce) ; Barto, Libor (oponent)
Tato práce se zabývá dvěma ekvivalentními reformulacemi problému čtyř barev. První z nich ukazuje spojitost barvení grafů s vektorovým součinem, druhá na ni navazuje a rozvíjí souvislost s formální gramatikou. Tyto reformulace a důkazy jejich ekvivalence s větou o čtyřech barvách jsou výsledky dvou prací, jejichž motivací je snaha o jednodušší důkaz slavného problému, který byl zatím dokázán jen za pomoci počítače. Přinášejí zajímavý úhel pohledu na problém barvení grafů a nabízejí možnost, jak jej uchopit novým způsobem, který by se mohl ukázat přístupnějším. Tato práce představí důkazy uvedené ve výchozí literatuře a doplní kroky, které tam nejsou podrobně zpracovány. Některé myšlenky se pokusí více formalizovat a přispět tak k lepší srozumitelnosti důkazů. 1
|
|
|
Combinatorial Gap Label Cover
Bialas, Filip ; Barto, Libor (vedoucí práce) ; Kompatscher, Michael (oponent)
Věty o pravděpodobnostně ověřitelných důkazech (PCP) jsou známé těžké výsledky z teoretické informatiky. Konstruují pravděpodobnostně ověřitelné důkazové systémy se zajímavými a překvapivými vlastnostmi a jsou využívány k důkazům NP-těžkosti mnoha aproximačních problémů. Slabší kombinatorická verze jedné z vět této teorie (Gap La- bel Cover) byla nedávno dokázána s použitím pouze kombinarických postupů. Po shrnutí hlavních výsledků klasické PCP teorie se důkladně zaobírám touto kombinatorickou verzí. Originálními výsledky této práce jsou protipříklady k očekávanému chování dvou kon- ceptů z klasické teorie v kombinatorickém světě - pravděpodobnostní verze a paralelního opakování. 1
|
|
| |
|
|
Clones of tournaments
Boroš, Martin ; Barto, Libor (vedoucí práce) ; Kompatscher, Michael (oponent)
V této práci studujeme klony turnajů. Práce je rozdělena do tří částí. V první části poskytneme základní definice a fakta, která budeme potřebovat ve zbytku práce. V druhé části budeme studovat klon tzv. Rock-Paper-Scissors algebry. Poskytneme jeho úplnou charakterizaci. Ve třetí části se pokusíme zobecnit poznatky z druhé části. Dokážeme, že jednoduchý turnaj nemá žádné netriviální subdirektní relace. Pomocí tohoto výsledku pak budeme schopni podat částečnou charakterizaci klonu libovolného turnaje. Na konec dokážeme, že každý jednoduchý turnaj je funkcionálně úplný. 1
|
|
| |
|
| |
host ::
RSS.