|
|
Proof Complexity of CSP
Gaysin, Azza ; Krajíček, Jan (advisor) ; Kolokolova, Antonina (referee) ; Kompatscher, Michael (referee)
In this thesis we formalize Zhuk's decision algorithm solving in p-time tractable con- straint satisfaction problems (CSPs) in a weak theory of bounded arithmetic W1 1 . As a consequence, we show that tautologies that express the negative instances of such CSPs have polynomial proofs in the quantified propositional calculus G. 1
|
|
|
Spectrum problem
Krejčí, Markéta ; Krajíček, Jan (advisor) ; Kompatscher, Michael (referee)
In this thesis we present the notion of a spectrum of a first-order sentence, including several theorems linking it to computational complexity theory and well-known open problems of Scholz and Asser. We show that there are some interesting subsets of N+ that form a spectrum - either by a direct construction or by applying more advanced theorems. Finally, we prove that spectra are closed under union, intersection, addition and multiplication. 1
|
|
|
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
|
|
|
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
|
|
|
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
|
|
|
The incompleteness theorems and Berry's paradox
Grego, Maroš ; Krajíček, Jan (advisor) ; Kompatscher, Michael (referee)
This thesis is devoted to a formal presentation of an alternative proof of Gödel's first incompleteness theorem, based on the Berry paradox ("the smallest number not definable in under 57 characters", with this definition having less characters and defining this number). The approach used was suggested by an article by G. Chaitin. We define the Kolmogorov complexity of a natural number m as the binary length of the smallest program for the universal Turing machine that on input 0 outputs the number m. Using a formal argument based on the Berry paradox, we show that the property of a (large enough) number n being a lower bound for the Kolmogorov complexity of a number m is not provable in any consistent recursively axiomatizable extension of Robinson arithmetic. But by a counting argument, for all n, it is true for all but finitely many m. This is used to prove the first incompleteness theorem. Another way (by G. S. Boolos) of formalizing the Berry paradox to prove the same theorem is put in the context of the presented approach. 1
|
|
|
Logic circuits as models of computation
Naumenko, Mykhailo ; Kazda, Alexandr (advisor) ; Kompatscher, Michael (referee)
This work focuses on the study of logic circuits. We investigated the basics of the theory of logic circuits following the textbook "Models of Computation" by John E. Savage and we used this knowledge to solve some of the examples and problems suggested in the textbook. In this work, you can find key concepts related to logical circuits. Our main topic is the estimation of the lower bounds of the circuit size and formula size of general Boolean function. We constructed simple examples of some known circuits and showed how the circuit designs may be offered. 1
|
guest ::
