|
| |
|
| |
|
| |
|
| |
|
| |
|
|
Algebraický přístup k CSP
Bulín, Jakub ; Barto, Libor (advisor) ; Růžička, Pavel (referee)
For a finite relational structure A, the Constraint Satisfaction Problem with template A, or CSP(A), is the problem of deciding whether an input relational structure X admits a homomorphism to A. The CSP dichotomy conjecture of Feder and Vardi states that for any A, CSP(A) is either in P or NP-complete. In the first part we present the algebraic approach to CSP and summarize known results about CSP for digraphs, also known as the H-coloring problem. In the second part we study a class of oriented trees called special polyads. Using the algebraic approach we confirm the dichotomy conjecture for special polyads. We provide a finer description of the tractable cases and give a construction of a special polyad T such that CSP(T) is tractable, but T does not have width 1 and admits no near-unanimity polymorphisms.
|
|
|
Homomorphisms into unary algebras
Škrobánek, Jiří ; Barto, Libor (advisor) ; Bulín, Jakub (referee)
This thesis studies the computational complexity of constraint satisfaction problem (CSP) over structures with unary operations (unary algebras). We concentrate on a special class of such CSPs, so called reversing problems. We present a new proof of complexity classification for reversing problems, which uses the algebraic approach based on studying polymorphisms. We show that some reversing problems admit near unanimity polymorphisms (and are therefore solvable in polynomial time) while the remaining reversing problems do not admit weak near unanimity polymorphisms (and are therefore NP-complete).
|
|
|
The Number of Homomorphisms to a Fixed Algebra
Kapytka, Maryia ; Barto, Libor (advisor) ; Stanovský, David (referee)
In this work we give a partial answer to the following question: For which fixed finite algebras A is the number of homomorphisms from a similar algebra X to A bounded from above by a polynomial in the size of X? The work is divided into two parts: Preliminaries and Results. In the first part we introduce the reader to this topic and give some basic facts about the number of homomorphisms. In the main part we generalize the case of a two-element semilattice to a general finite semilattice, then we look at a specific three- element algebra with a majority operation and a specific three-element 2-semilattice, the rock-paper-scissors algebra. Then we study groups. Finally we consider unary algebras. All the algebras mentioned above apart from unary algebras give a positive answer to our question. 1
|
|
|
Monotone functions avoiding majorities
Petr, Jan ; Barto, Libor (advisor) ; Mottet, Antoine (referee)
In the past five years, the Promise Constraint Satisfaction Problem (PCSP) has been a popular topic in computational complexity, covering a wide range of computational problems. In this work, we begin by introducing the PCSP and then turn our atten- tion to the still open problem of the PCSP over 'monotone folded Boolean structures'. Brakensiek and Guruswami showed in 2016 that the PCSP is in P if all odd majorities are polymorphisms between structures under consideration. We focus on the situation in which some of the odd majorities are not among the polymorphisms. We present a technique for proving NP-completeness of PCSPs that uses the notion of heavy sets. Our approach succeeds in proving that the absence of the 3-majority makes the PCSP NP-complete. We then give a few partial results for the case of the absence of the 5-majority. We finish by determining the size of the smallest heavy set for a particular family of functions. 1
|
|
|
Generalizing CSP-related results to infinite algebras
Olšák, Miroslav ; Barto, Libor (advisor) ; Zhuk, Dmitrii (referee) ; Pinsker, Michael (referee)
The recent research on constraint satisfaction problems (CSPs) on fixed finite templates provided useful tools for computational complexity and universal algebra. However, the research mainly focused on finite relational structures, and consequently, finite algebras. We pursue a generalization of these tools and results into the domain of infinite algebras. In particular, we show that despite the fact that the Maltsev condition s(r, a, r, e) = s(a, r, e, a) does not characterize Taylor algebras (i.e., algebras that satisfy a nontrivial idem- potent Maltsev condition) in general, as it does in the finite case, there is another strong Maltsev condition characterizing Taylor algebras, and s(r, a, r, e) = s(a, r, e, a) characterizes another interesting broad class of algebras. We also provide a (weak) Maltsev condition for SD(∧) algebras (i.e., algebras that satisfy an idem- potent Maltsev condition not satisfiable in a module). Beyond Maltsev conditions, we study loop lemmata and, in particular, reprove a well known finite loop lemma by two different general (infinite) approaches.
|
guest ::
