|
|
Proof Complexity of CSP
Gaysin, Azza ; Krajíček, Jan (vedoucí práce) ; Kolokolova, Antonina (oponent) ; Kompatscher, Michael (oponent)
V této práce formalizujeme Zhukův polynomiální algoritmus rozhodující řešitelnost problémů splňování podmínek (CSPs), které nejsou NP-úplné, ve slabé teorii omezené aritmetiky W1 1 . Jako důsledek odvodíme, že tautologie odpovídající negativním instancím oněch CSP mají polynomiální důkazy v kvantifikovaném výrokovém počtu G. 1
|
|
|
Spectrum problem
Krejčí, Markéta ; Krajíček, Jan (vedoucí práce) ; Kompatscher, Michael (oponent)
V této práci prezentujeme pojem spektra sentence logiky prvního řádu včetně nekolika vět spojujících ho s teorií složitosti a dvou známých otevřených problémů Scholze a Assera. Ukážeme, že jsou některé zajimavé podmnožiny N+ , které tvoří spektrum - buď přímou kontrukcí nebo za použití pokročilejších vět. Nakonec dokážeme, že spektra jsou uzavřená na sjednocení, průnik, sčítání a násobení. 1
|
|
|
Symmetric terms
Boroš, Martin ; Barto, Libor (vedoucí práce) ; Kompatscher, Michael (oponent)
V této práci studujeme symetrické relace a symetrické afinní podprostory Z ([n] k ) p . Práce je rozdělena na tři části. V první části poskytneme základní definice a fakta která jsou potřeba ve zbytku práce. V druhé části studujeme symetrické afinní podprostory Z ([n] k ) p . Dokážeme úplnou charakterizaci symetrických vektorových podprostorů v případě k = 2. Pomocí tohoto výsledku podáme charakterizaci toho, kdy každý symetrický afinní podprostor obsahuje konstantu pro k = 2. Ve třetí části studujeme symetrické relace algebry. Dokážeme, že za určitých předpokladů má algebra k-WNU termovou operaci. 1
|
|
|
Combinatorial Gap Label Cover
Bialas, Filip ; Barto, Libor (vedoucí práce) ; Kompatscher, Michael (oponent)
Věty o pravděpodobnostně ověřitelných důkazech (PCP) jsou známé těžké výsledky z teoretické informatiky. Konstruují pravděpodobnostně ověřitelné důkazové systémy se zajímavými a překvapivými vlastnostmi a jsou využívány k důkazům NP-těžkosti mnoha aproximačních problémů. Slabší kombinatorická verze jedné z vět této teorie (Gap La- bel Cover) byla nedávno dokázána s použitím pouze kombinarických postupů. Po shrnutí hlavních výsledků klasické PCP teorie se důkladně zaobírám touto kombinatorickou verzí. Originálními výsledky této práce jsou protipříklady k očekávanému chování dvou kon- ceptů z klasické teorie v kombinatorickém světě - pravděpodobnostní verze a paralelního opakování. 1
|
|
|
Clones of tournaments
Boroš, Martin ; Barto, Libor (vedoucí práce) ; Kompatscher, Michael (oponent)
V této práci studujeme klony turnajů. Práce je rozdělena do tří částí. V první části poskytneme základní definice a fakta, která budeme potřebovat ve zbytku práce. V druhé části budeme studovat klon tzv. Rock-Paper-Scissors algebry. Poskytneme jeho úplnou charakterizaci. Ve třetí části se pokusíme zobecnit poznatky z druhé části. Dokážeme, že jednoduchý turnaj nemá žádné netriviální subdirektní relace. Pomocí tohoto výsledku pak budeme schopni podat částečnou charakterizaci klonu libovolného turnaje. Na konec dokážeme, že každý jednoduchý turnaj je funkcionálně úplný. 1
|
|
|
The incompleteness theorems and Berry's paradox
Grego, Maroš ; Krajíček, Jan (vedoucí práce) ; Kompatscher, Michael (oponent)
Tahle práce je věnovaná formální prezentaci alternativního důkazu Gödelovy první věty o neúplnosti, založeném na Berryho paradoxu ("nejmeší číslo, které nelze defino- vat méně než 57 znaky", přičemž tahle definice má méně znaků a definuje tohle číslo). Použitý přístup byl navržen v článku G. Chaitina. Definujeme Kolmogorovovu složitost přirozeného čísla m jako binární délku nejmešího programu pro univerzální Turingův stroj, který na vstupu 0 vrátí číslo m. Pomocí formálního argumentu inspirovaného Berryho paradoxem ukážeme nedokazatelnost tvrzení, že číslo n je dolní mezí pro Kol- mogorovovu složitost čísla m v jakémkoliv konzistentím rekurzivně axiomatizovatelném rozšíření Robinsonovy aritmetiky. Jednoduchý početní argument ale ukáže, že pro všechna n je tohle tvrzení pravdivé pro všechna až na konečně mnoho m. To je využito k důkazu první věty o neúplnosti. Jiný způsob (pocházející od G. S. Boolose) formalizace Berryho paradoxu k důkazu stejné věty je představen v kontextu prezentovaného přístupu. 1
|
|
|
Logic circuits as models of computation
Naumenko, Mykhailo ; Kazda, Alexandr (vedoucí práce) ; Kompatscher, Michael (oponent)
Tato práce se zaměřuje na studium logických obvodů. Vykládáme v ní teorii logických obvodů podle učebnice "Models of Computation" od Johna E. Savage a řešíme některé úlohy a cvičení z této učebnice. V této práci najdete klíčové pojmy související s logickými obvody. Věnovali jsme znač- nou pozornost hlavně odhadům dolních mezí velikostí obvodů a velikostí formulí obecných booleovských funkcí. Sestrojili jsme také několik jednoduchých příkladů známých obvodů a ukázali jsme, jak lze navrhnout další obvody. 1
|
host ::
RSS.