|
|
Kombinatorika matematických struktur
Paták, Pavel ; Krajíček, Jan (advisor) ; Thapen, Neil (referee)
The combinatorics of a first order mathematical structure is the class of all formulas valid in all in it definable structures. This notion was first introduced by Kraj'ček in [6]. In the present work we try to characterize and compare the combinatorics of several different prominent structures (reals, complex number, dense linear order, . . . ). We also study the question of algorithmical complexity, i.e. the question how hard it is to check whether a given formula lies in the combinatorics of a given structure. We prove that this question is corecursively enumeratively complete and therefore algorithmicaly undecidable in the case of models of complete theories without strict order property (SOP) and in the case of pseudofinite structures.
|
|
| |
|
|
Definability in mathematical structures
Paták, Pavel ; Krajíček, Jan (advisor) ; Jeřábek, Emil (referee)
Nazev pram: Defiuovatelnost v matrnnatickych struktnrneh Auiur: Pave! Patak Kat.odra: Katedra algebry Vedouci bakalafske prace: Prof. R.XDr. Jan Krajicek, DrSc. e-mail vedouciho: krajicek'Q'math.cas.cz AbytrakL: V pfedlo/.ene praci so zabyvame popisem definovatelnych nmozin v ruznych matematickych st.rukturaeh. Ukazujerne, zo defiuovatelne mnoziny v pfirozenych, celych a racionalnich cfslcch inohon byt volico kompliko- vann. naproti toinn dnfiiiovatolnr mnoziny ve .striiktnrach s {'liininari kvanti- fikatoru (reaina, komplexni cfsla,. - . ) JHOU jcdnoduclic. Vciinjoino se i pojinu modolovo I'iplnosti. S poinoci zfskanych poznatku a vo.ty o nplno.sti pak snadno dokazeme nektere obtizne vety jinych disciplin - alji,ebraickou Xnll- stollcnsatz a Artinovn charaktorizaci pozitivnr dofinitnicb racionalnfcli fimkoi, geometrickou Tarski-Seidenbergovn vetn a ninohc dalyi. Klicova slova: nmtematicke sl.rnktnry, dcliiiuvatelnost, eliminace kvantilika- toru Title: DcfinnViility in inatlioinatica.l structures Author: Pavel Patak Department: Department of Algebra Supervisor: Prof. RNDr. Jan Krajirek, DrSc. Supervisor's e-mail address: kra.jicokv'iJina.lb.cas.cz Abstract: In t,be present work we study the description of definable sets in various mathematical structures. We show that, the definable sets in natural, integer...
|
|
|
NP vyhledávací problémy
Jirotka, Tomáš ; Krajíček, Jan (advisor) ; Pudlák, Pavel (referee)
Title: NP search problems Author: Tomáš Jirotka Department: Department of Algebra Supervisor: Prof. RNDr. Jan Krajíček, DrSc. Abstract: The thesis summarizes known results in the field of NP search pro- blems. We discuss the complexity of integer factoring in detail, and we propose new results which place the problem in known classes and aim to separate it from PLS in some sense. Furthermore, we define several new search problems. Keywords: Computational complexity, TFNP, integer factorization. 1
|
|
|
Model constructions for bounded arithmetic
Garlík, Michal ; Krajíček, Jan (advisor) ; Buss, Samuel (referee) ; Thapen, Neil (referee)
Title: Model constructions for bounded arithmetic Author: Michal Garlík Abstract: We study constructions of models of bounded arithmetic theories. Us- ing basic techniques of model theory we give a new proof of Ajtai's completeness theorem for nonstandard finite structures. Working in the framework of restricted reduced powers (a generalization of the ultrapower construction) we devise two methods of constructing models of bounded arithmetic. The first one gives a new proof of Buss's witnessing theorem. Using the second method we show that the theory R1 2 is stronger than its variant strictR1 2 under a plausible computational assumption (the existence of a strong enough one-way permutation), and that the theory PV1 + Σb 1(PV ) − LLIND is stronger than PV1 + strictΣb 1(PV ) − LLIND under the same assumption. Considering relativized theories, we show that R1 2(α) is stronger than strictR1 2(α) (unconditionally). 1
|
|
| |
|
| |
|
|
Výroková logika a algebra
Polach, František ; Krajíček, Jan (advisor) ; Pudlák, Pavel (referee)
Algebraic proof systems of which the most important are the polynomial calculus and the Nullstellensatz proof system are proof systems that use algebraic means for proving propositional tautologies - they are based on polynomial identities over (commutative) rings. Razborov [9] have proved a non-trivial lower bound on degree for polynomia calculus proofs of the tautologies (a set of polynomials) that express the pigeonhole principle over any field. This work gathers present important results for algebraic proof systems and generalizes the Razborov's construction used in his proof of the lower bound to another set of polynomials. We explicitly describe the basis of the vector space of polynomials that are derivable by a small degree polynomial calculus proof from the tautologies that express a variant of the pigeonhole principle (that generalizes the principle for multifunctions).
|
|
|
Vyhledávací problémy a hledání kolizí pro hašovací funkce
Čarnoký, Samuel ; Krajíček, Jan (advisor) ; Pudlák, Pavel (referee)
Title: Search problems and search for collisions in hash functions Author: Samuel Čarnoký Department: The Department of Algebra Supervisor: prof. RNDr. Jan Krajíček, DrSc. Supervisor's e-mail address: krajicek@karlin.mff.cuni.cz Abstract: Central points of this work are NP search problems and the existence of reductions amog them in the relativised world. Absolute separation would separate N from NP. In particular, we talk about the problem of finding collisions in hash functions that must exist due to the famous pigeonhole principle. We present a brief introduction into the topic, we define various NP search problems and recall reductions and separations. Reduction of weak version of PHP to a problem of finding a homogeneous subgraph is described and our own results are presented in the form of reduction of another variant of PHP to a problem related to finding paths in a graph. We talk about reducing the task of finding collisions in multiple functions into finding a collision in one function. Keywords: NP search, reductions, pigeonhole principle, oracles
|
|
|
NetHack Bot Framework
Krajíček, Jan ; Gemrot, Jakub (advisor) ; Mráz, František (referee)
Previous attempts at implementing bots for the classic roguelike game NetHack have been hindered by many problems related to its complexity and console-based interface. The framework implemented as part of this work solves the problem of interfacing with the game and provides a programmer-friendly API for the Java and Clojure programming languages. It enables programming sophisticated bots using the provided model of the game world, a library of possible actions and utilities for various aspects of the game. The framework uses elements of functional and logic programming and doesn't require modifications of the game. Also described is an implementation of the first NetHack bot capable of winning the game. Powered by TCPDF (www.tcpdf.org)
|
guest ::
RSS feed.