|
|
Promises in Satisfaction Problems
Asimi, Kristina ; Barto, Libor (advisor) ; Barnaby, Martin (referee) ; Živný, Stanislav (referee)
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 (advisor) ; Zhuk, Dmitrii (referee)
This thesis provides a classification of the minion homomorphism preordering and minion cores within a class of multi-sorted Boolean clones. These clones can be described as those clones defined on the set {0, 1}k = {0, 1} × {0, 1} × · · · × {0, 1}, where the clone operations act component-wise on the k-tuples, which are determined by multi-sorted unary or binary relations. The second chapter of this thesis focuses on presenting the key findings. We introduce specific minion cores and establish the preordering among them. Furthermore, we prove that each clone falling under the aforementioned type is equivalent to one of these minion cores.
|
|
|
Symmetric terms
Boroš, Martin ; Barto, Libor (advisor) ; Kompatscher, Michael (referee)
In this thesis, we study symmetric relations and affine symmetric subspaces of Z ([n] k ) p . The thesis is divided into three parts. In the first part, we provide the basic definitions and facts that are needed in the rest of the thesis. In the second part, we study symmetric affine subspaces of Z ([n] k ) p . We will provide a full characterization of symmetric vector subspaces when k = 2. Using that result, we will give a characterization of when every symmetric affine subspace contains a constant for k = 2. In the third part, we study the symmetric relations of an algebra. We will prove that under some assumptions an algebra has a k-WNU term operation. 1
|
|
|
Minimal Taylor Clones on Three Elements
Jankovec, Filip ; Barto, Libor (advisor)
Brady have classified all the minimal Taylor algebras on a three-element set up to term equivalence and isomorphism; there are 24 such algebras. The thesis studies the clones of these algebras. For 12 of them, the thesis characterizes operations in the clone and, also, describes the clone by means of relations. 1
|
|
|
Graph coloring and formal grammars
Elichová, Sára ; Holub, Štěpán (advisor) ; Barto, Libor (referee)
This thesis deals with two equivalent reformulations of the four color problem. The first of them shows the connection between graph coloring and the vector cross product; the se- cond one expands on it and develops a relation to a formal grammar. These reformulations together with the proofs of their equivalence to the four color theorem are the results of two articles motivated by the effort to find a simpler proof of the famous problem, which was proved only by computer. They bring an interesting perspective on the problem of graph coloring and give the possibility to look on it in a new way, which could turn out to be more approachable. This thesis presents the proofs introduced in the source li- terature and adds the steps that are not elaborated in detail by the authors. It aims to formalize some of the ideas and to contribute to the comprehensibility of the proofs. 1
|
|
|
Combinatorial Gap Label Cover
Bialas, Filip ; Barto, Libor (advisor) ; Kompatscher, Michael (referee)
Theorems about probabilistically checkable proofs (PCP) are famous hard-to-prove results from the theoretical computer science. They provide constructions of PCP sys- tems with interesting surprising properties and serve as a starting point for proofs of NP-hardness of many approximation problems. Recently, a weaker combinatorial version of one of these theorems (Gap Label Cover) was proved using only combinatorial tools. After summarizing the main results in the classical PCP theory, I explore the combina- torial version thoroughly. Original results of this thesis consist of counterexamples to the expected behavior of two concepts from the classical theory in the combinatorial setting - probabilistic version and parallel repetition. 1
|
|
|
Minimal Taylor Clones on Three Elements
Jankovec, Filip ; Barto, Libor (advisor) ; Zhuk, Dmitrii (referee)
Brady have classified all the minimal Taylor algebras on a three-element set up to term equivalence and isomorphism; there are 24 such algebras. The thesis studies the clones of these algebras. For 12 of them, the thesis characterizes operations in the clone and, also, describes the clone by means of relations. 1
|
|
|
Clones of tournaments
Boroš, Martin ; Barto, Libor (advisor) ; Kompatscher, Michael (referee)
In this thesis, we study the clones of tournaments. The thesis is divided into three parts. In the first part, we provide the basic definitions and facts that are needed in the rest of the thesis. In the second part, we study the clone of the Rock-Paper-Scissors algebra. We will provide a full characterization. In the third part, we attempt to gener- alize the results from the second part. We will prove that a simple tournament does not have non-trivial subdirect relations. Using that result, we will give a partial characteri- zation of the clone of any tournament. Lastly, we will prove that simple tournaments are functionally complete. 1
|
|
| |
|
| |
guest ::
