Název: Konstrukce modelů omezené aritmetiky
Překlad názvu: Model constructions for bounded arithmetic
Autoři: Garlík, Michal ; Krajíček, Jan (vedoucí práce) ; Buss, Samuel (oponent) ; Thapen, Neil (oponent)
Typ dokumentu: Disertační práce
Rok: 2015
Jazyk: eng
Abstrakt: [eng] [cze]
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 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
Klíčová slova: formální teorie; nestandardní model; třída složitosti; complexity class; formal theory; nonstandard model

Instituce: Fakulty UK (VŠKP) (web)
Informace o dostupnosti dokumentu: Dostupné v digitálním repozitáři UK.
Původní záznam: http://hdl.handle.net/20.500.11956/81347

Trvalý odkaz NUŠL: http://www.nusl.cz/ntk/nusl-481828


Záznam je zařazen do těchto sbírek:
Školství > Veřejné vysoké školy > Univerzita Karlova > Fakulty UK (VŠKP)
Vysokoškolské kvalifikační práce > Disertační práce