|
|
Tennenbaum phenomena in models of arithmetic
Kriško, Lukáš ; Thapen, Neil (vedoucí práce) ; Bulín, Jakub (oponent)
Hlavným cieľom tohto textu je skúmať, či už prezentovaním známych výsledkov alebo našich vlastných, niektoré aritmetické funkcie a relácie z pohľadu ich rekurzívnosti v spočetných neštandardných modeloch Peanovej aritmetiky, skratkou PA, alebo niekt- orého jej slabšieho fragmentu ako I∆0 alebo IΣ1. V prvej časti prezentujeme Tennenbaumovu vetu, ktorá je známym výsledkom danej oblasti. Veta tvrdí, že v každom neštandardnom modeli M, Peanovej aritmetiky, s doménou N nemôže byť +M ani ×M rekurzívnou funkciou. Navyše, prezentujeme daný výsledok pre + v silnejšie podobe a to pre teóriu I∆0, daný výsledok pochádza od K. McAloona. Aby sme ukázali že nie je všetko stratené, prezentujem ďalší známy výsledok tvrdiaci, že relácia < a funkcia nasledovník, S, môžu byť simultánne rekurzívne v nejakom neštandardnom modeli PA s doménou N. V druhej časti prezentujeme naše vlastné výsledky ktoré sme dostali pýtaním sa otázok o rekurzívnosti funkcií x div y, celočíselné delenie, a x mod y, zvyšok po celočíselnom delení, v modeloch PA. Taktiež častokrát uvažujeme reštrikcie x div y a x mod y na x div n a x mod n, kde n je štandardné číslo. Aby sme spomenuli niekoľko výsledkov ku ktorým sme prišli, ukázali sme, že neexistuje neštandardný model PA kde by boli obe funkcie x div n a x mod n rekurzívne. Ďalej, nemôže existovať...
|
|
| |
|
|
Kombinatorika matematických struktur
Paták, Pavel ; Krajíček, Jan (vedoucí práce) ; Thapen, Neil (oponent)
Kombinatorika matematické struktury prvního řádu je třída všech formulí, které platí ve všech strukturách v ní definovatelných. Tento pojem poprvé zavedl Krajíček v [6]. V předložené práci se zabýváme charakterizací a srovnáním kombinatorik známých matematických struktur (reálná a komplexní čísla, husté lineární uspořádání, ...). Dále se věnujeme otázce výpočetní složitosti, tj. otázce, jak těžké je zjistit, zda daná formule leží v kombinatorice dané struktury. Dokážeme, že v případě modelů úplných teorií bez vlastnosti striktního uspořádání (SOP) či v případě pseudokonečných struktur je tento problém korekurzivně spočetně úplný a tudíž algoritmicky neřešitelný.
|
|
|
Model constructions for bounded arithmetic
Garlík, Michal ; Krajíček, Jan (vedoucí práce) ; Buss, Samuel (oponent) ; Thapen, Neil (oponent)
Název práce: Konstrukce modelů omezené aritmetiky Autor: Michal Garlík Abstrakt: Studujeme konstrukce modelů teorií omezené aritmetiky. Pomocí základních technik teorie modelů podáme nový důkaz Ajtaiovy věty o úplnosti pro nestandardně konečné struktury. Za použití omezené redukované mocniny (zobecnění ultraproduktu) navrhneme dvě nové metody konstrukce modelů ome- zené aritmetiky. První dá nový důkaz Bussovy dosvědčující věty. Druhou metodou ukážeme, že teorie R1 2 je silnější než její varianta strictR1 2 za věrohodného výpo- četně-složitostního předpokladu (existence dostatečně silné jednosměrné permu- tace) a že za stejného předpokladu je teorie PV1 + Σb 1(PV ) − LLIND silnější než PV1 + strictΣb 1(PV ) − LLIND. Pro relativizované teorie dokážeme, že R1 2(α) je silnější strictR1 2(α) (bez dodatečného předpokladu). 1
|
|
|
On the Power of Weak Extensions of V0
Müller, Sebastian Peter ; Krajíček, Jan (vedoucí práce) ; Thapen, Neil (oponent) ; Kolodziejczyk, Leszek (oponent)
Název práce: O síle slabých rozšírení teorie V0 Autor: Sebastian Müller Katedra: Katedra Algebry Vedoucí disertační práce: Prof. RNDr. Jan Krajíček, DrSc., Katedra Algebry. Abstrakt: V predložené disertacní práci zkoumáme sílu slabých fragmentu arit- metiky. Činíme tak jak z modelově-teoretického pohledu, tak z pohledu důkazové složitosti. Pohled skrze teorii modelu naznačuje, že malý iniciální segment libo- volného modelu omezené aritmetiky bude modelem silnější teorie. Jako příklad ukážeme, že každý polylogaritmický řez modelu V0 je modelem VNC. Užitím známé souvislosti mezi fragmenty omezené aritmetiky a dokazatelností v ro- zličných důkazových systémech dokážeme separaci mezi rezolucí a TC0 -Frege systémem na náhodných 3CNF-formulích s jistým poměrem počtu klauzulí vůci počtu proměnných. Zkombinováním obou výsledků dostaneme slabší separační výsledek pro rezoluci a Fregeho důkazové systémy omezené hloubky. Klíčová slova: omezená aritmetika, důkazová složitost, Fregeho důkazový systém, Fregeho důkazový systém omezené hloubky, rezoluce Title: On the Power of Weak Extensions of V0 Author: Sebastian Müller Department: Department of Algebra Supervisor: Prof. RNDr. Jan Krajíček, DrSc., Department of Algebra....
|
|
|
Logika a kryptografie
Wagner, Vojtěch ; Krajíček, Jan (vedoucí práce) ; Thapen, Neil (oponent)
Název práce: Logika a kryptografie Autor: Bc. Vojtěch Wagner Katedra: Katedra algebry Vedoucí diplomové práce: prof. RNDr. Jan Krajíček, DrSc. Abstrakt: Práce se zabývá studiem metod pro formalizaci kryptografických konstrukcí. Konkrétně metodou, která je založena na definování logické teorie T, která obsahuje řetězce, čísla a objekty třídy k - k-ární funkce. Povolíme jim určité operace a formulujeme axiomy, termy a formule. Budeme používat speciální typ termů - počítající term, který označuje počet prvků x v daném inter- valu splňujících formuli ϕ(x). Díky nim můžeme mluvit o pravděpodobnostech a používat další pojmy z teorie pravděpodobnosti. Práce nejprve popisuje detailně tuto teorii. Poté přináší formalizaci Goldreich-Levinovy věty. Cílem práce je předložit potřebné kryptografické pojmy a konstrukce v jazyce teorie T a následně dokázat větu pomocí objektů, pravidel a axiomů teorie T. Uvedené definice a principy jsou ilustrovány na příkladech. Cílem práce je ukázat, že takováto teorie je dostatečně silná, aby dokázala správnost a bezpečnost podobné kryptografické konstrukce. Klíčová slova: kryptografie, ověřování protokolů, věta o správnosti, formální logická teorie, Goldreich-Levinova věta 1
|
|
|
Model constructions for bounded arithmetic
Garlík, Michal ; Krajíček, Jan (vedoucí práce) ; Buss, Samuel (oponent) ; Thapen, Neil (oponent)
Název práce: Konstrukce modelů omezené aritmetiky Autor: Michal Garlík Abstrakt: Studujeme konstrukce modelů teorií omezené aritmetiky. Pomocí základních technik teorie modelů podáme nový důkaz Ajtaiovy věty o úplnosti pro nestandardně konečné struktury. Za použití omezené redukované mocniny (zobecnění ultraproduktu) navrhneme dvě nové metody konstrukce modelů ome- zené aritmetiky. První dá nový důkaz Bussovy dosvědčující věty. Druhou metodou ukážeme, že teorie R1 2 je silnější než její varianta strictR1 2 za věrohodného výpo- četně-složitostního předpokladu (existence dostatečně silné jednosměrné permu- tace) a že za stejného předpokladu je teorie PV1 + Σb 1(PV ) − LLIND silnější než PV1 + strictΣb 1(PV ) − LLIND. Pro relativizované teorie dokážeme, že R1 2(α) je silnější strictR1 2(α) (bez dodatečného předpokladu). 1
|
|
|
The BSS model and cryptography
Hostáková, Kristina ; Krajíček, Jan (vedoucí práce) ; Thapen, Neil (oponent)
Real numbers are usually represented by various discrete objects such as floating points or partial decimal expansions. This is mainly because the clas- sical computability theory relates to computers which work with discrete data. Nevertheless, for theoretical purposes it is interesting to look at models of com- putation that deal with real numbers as with objects of unit size. A very natural such model was suggested by Blum, Shub and Smale in 1989. In 2012 Grigoriev and Nikolenko studied various cryptographic tasks involv- ing real numbers (for example, biometric authentication) and they considered the BSS machine model. In this work we focus on hard to invert functions in this model of computation. Our main theme is to analyse whether there are real functions of one variable that are easier to compute than to invert by a BSS machine. 1
|
|
|
On the Power of Weak Extensions of V0
Müller, Sebastian Peter ; Krajíček, Jan (vedoucí práce) ; Thapen, Neil (oponent) ; Kolodziejczyk, Leszek (oponent)
Název práce: O síle slabých rozšírení teorie V0 Autor: Sebastian Müller Katedra: Katedra Algebry Vedoucí disertační práce: Prof. RNDr. Jan Krajíček, DrSc., Katedra Algebry. Abstrakt: V predložené disertacní práci zkoumáme sílu slabých fragmentu arit- metiky. Činíme tak jak z modelově-teoretického pohledu, tak z pohledu důkazové složitosti. Pohled skrze teorii modelu naznačuje, že malý iniciální segment libo- volného modelu omezené aritmetiky bude modelem silnější teorie. Jako příklad ukážeme, že každý polylogaritmický řez modelu V0 je modelem VNC. Užitím známé souvislosti mezi fragmenty omezené aritmetiky a dokazatelností v ro- zličných důkazových systémech dokážeme separaci mezi rezolucí a TC0 -Frege systémem na náhodných 3CNF-formulích s jistým poměrem počtu klauzulí vůci počtu proměnných. Zkombinováním obou výsledků dostaneme slabší separační výsledek pro rezoluci a Fregeho důkazové systémy omezené hloubky. Klíčová slova: omezená aritmetika, důkazová složitost, Fregeho důkazový systém, Fregeho důkazový systém omezené hloubky, rezoluce Title: On the Power of Weak Extensions of V0 Author: Sebastian Müller Department: Department of Algebra Supervisor: Prof. RNDr. Jan Krajíček, DrSc., Department of Algebra....
|
|
|
Kombinatorika matematických struktur
Paták, Pavel ; Krajíček, Jan (vedoucí práce) ; Thapen, Neil (oponent)
Kombinatorika matematické struktury prvního řádu je třída všech formulí, které platí ve všech strukturách v ní definovatelných. Tento pojem poprvé zavedl Krajíček v [6]. V předložené práci se zabýváme charakterizací a srovnáním kombinatorik známých matematických struktur (reálná a komplexní čísla, husté lineární uspořádání, ...). Dále se věnujeme otázce výpočetní složitosti, tj. otázce, jak těžké je zjistit, zda daná formule leží v kombinatorice dané struktury. Dokážeme, že v případě modelů úplných teorií bez vlastnosti striktního uspořádání (SOP) či v případě pseudokonečných struktur je tento problém korekurzivně spočetně úplný a tudíž algoritmicky neřešitelný.
|
host ::
RSS.