|
|
Tennenbaum phenomena in models of arithmetic
Kriško, Lukáš ; Thapen, Neil (advisor) ; Bulín, Jakub (referee)
The main aim of this text is to present and investigate some basic arithmetical func- tions and relations with regard to being recursive in a countable non-standard model of Peano arithmetic, PA for short, or some weaker fragment, like I∆0 or IΣ1, of PA. In PART I, we present a known result called Tennenbaum's theorem. It states that every non-standard model M of PA with domain N can have neither +M nor ×M recursive. Moreover, we present the case for + in a strengthened version for I∆0, which is due to K. McAloon. To show that not everything is lost, we also present a well know result stating that < and the successor function can be simultaneously recursive in some non-standard model of PA with domain N. In PART II, we make our own investigation into the questions related to whether there can be a non-standard model of PA s.t. x div y, the quotient function, and x mod y, the remainder function, are recursive in it. Furthermore, we often restrict y to some standard number n. To give a non-exhaustive list of problems we have solved, we showed that there can be no non-standard model of PA with both x div n and x mod n recursive. Furthermore, there can be no non-standard model of IΣ1 with x div y recursive. On the other hand, x div n and x mod n can be separately recursive in a non-standard model of PA. 1
|
|
|
Squares in integer sequences
Hudcová, Barbora ; Holub, Štěpán (advisor) ; Bulín, Jakub (referee)
This work is based on an article which provides a construction of the first infinite word over a finite alphabet avoiding additive cubes. We construct other words with the same properties and we choose one of them to show the main idea of the proof that this word avoids additive cubes. 1
|
|
| |
|
|
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).
|
|
|
Higher commutators in loop theory
Semanišinová, Žaneta ; Stanovský, David (advisor) ; Bulín, Jakub (referee)
The thesis deals with supernilpotence in loops, building on three equivalent definitions of higher commutators in Mal'tsev algebras due to Aichinger and Mud- rinski, Bulatov and Opršal. In the thesis, we study identities that occur in 1-, 2- and 3-supernilpotent loops. We prove that a k-supernilpotent loop has a k- nilpotent multiplication group. Moreover, we present results of our implementa- tion of algorithmic testing of supernilpotence in non-associative loops of small orders.
|
|
|
Algebraický přístup k CSP
Bulín, Jakub
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.
|
|
|
Minimum 0-Extensions of Graph Metrics
Dvořák, Martin ; Bulín, Jakub (advisor) ; Majerech, Vladan (referee)
We consider the Minimum 0-Extension Problem for a given fixed undirected graph with positive weights. We study the computational com- plexity of the threshold decision variant with respect to properties of the fixed graph, in particular modularity and orientability, as defined by Karzanov in [Eur. J. Comb., 19/1 (1998)]. We approach the problem from the viewpoint of the Finite-Valued CSP, which allows us to employ the rich theory that was developed to prove the Dichotomy Conjecture. On the negative side, we provide an explicit reduction from the Max-Cut Problem to obtain NP-hardness for non-modular graphs. For non-orientable graphs, we express a cost function that satisfies a certain condition which guarantees the existence of an implicit reduction from the Max-Cut Problem. On the positive side, we construct symmetric fractional polymorphisms in order to show that the so-called Basic LP Relaxation can solve two special cases of weighted modular orientable graphs: paths and rectangles. 1
|
|
|
Permutation group algorithms
Plšková, Petra ; Bulín, Jakub (advisor) ; Růžička, Pavel (referee)
The Schreier Sims algorithm is a fundamental algorithm for permutation groups. Its purpose is to find a base and a strong generating set. Representation of a group using a base and a strong generating set is the core of many other algorithms. The aim of the thesis is to give the reader a detailed description of the algorithm. We present its pseudocode together with the pseudocode of its subroutines. We analyze the complexity with respect to the given pseudocode. Similarly, we describe an efficient, Monte Carlo version of the Schreier Sims algorithm whose time complexity is nearly linear. We give a detailed description of two improved algorithms for subroutines on which this version is based. We introduce the theoretical framework needed to support the correctness of both the deterministic and the probabilistic version of the algorithm. 1
|
|
|
Image reconstruction using graphical models
Ficová, Klára ; Kazda, Alexandr (advisor) ; Bulín, Jakub (referee)
Graphical models represent probability relations among random variables using a graph. They offer an effective way of modelling real life situations and are frequently used in machine learning and statistical thinking. The main goal of this thesis is to describe and implement techniques of denoising an image using graphical models. The graphical model we choose is factorgraph, representing pixels in image and interactions between them as nodes. Using algorithms on the graph, we determine the most probable true image. We also apply those theoretical methods on noisy images and compare the results. 1
|
guest ::
