|
|
NP vyhledávací problémy a redukce mezi nimi
Ševčíková, Renáta ; Krajíček, Jan (vedoucí práce) ; Pudlák, Pavel (oponent)
NP vyhledávací problémy a redukce mezi nimi Renáta Ševčíková V předložené práci studujeme třídu Total NP vyhledávacích problémů. Větší pozornost je věnována studiu podtříd této třídy a redukcí mezi nimi. Kombinujeme známé metody: vyhledávací stromy a jejich vztah k redukcím, důkaz sporem pomocí Nullstellensatz důkazového systému a dolní odhad na stupeň tohoto důkazu pomocí designů, abychom ukázali, že dvě třídy relativi- zovaných NP vyhledávacích problémů založených na Mod-p počítacím principu a Mod-q počítacím principu, kde p a q jsou různá prvočísla, nejsou mezi sebou redukovatelné. Práce je ukončena novým výsledkem separace pro p = 2 a q = 3.
|
|
|
DPLL algorithm and propositional proofs
Hrnčiar, Maroš ; Krajíček, Jan (vedoucí práce) ; Koucký, Michal (oponent)
Dôkazová zložitosť je zaujímavá súčasť matematiky nachádzajúca sa na pomedzí obrovskej oblasti logiky a teórie zložitosti. Skúma aké dôkazové systémy sú potrebné na efektívne dokazovanie rôznych matematických tvrdení. Predmetom tejto práce je spojenie medzi dôkazovými systémami a algoritmami na SAT. Uvidíme, že beh algoritmu na nesplniteľnej formule môže byť nahliadnutý ako výrokový dôkaz jej nesplniteľnosti, čím samotný algoritmus prakticky definuje celý dôkazový systém. Práca je určená najmä čitateľom so záujmom o dôkazovú zložitosť, ale dokáže aj samostatne objasniť princíp rezolúcie, či ponúknuť menej obvyklý pohľad na SAT, no zároveň predpokladá čitateľovu znalosť základov výrokovej logiky, teórie grafov a zložitosti.
|
|
| |
|
|
Těžké tautologie
Pich, Ján ; Krajíček, Jan (vedoucí práce) ; Pudlák, Pavel (oponent)
Skoumáme nedokazatelnost tvrzení NP$\not\subseteq$P/poly v různých fragmentech aritmetiky. Ta se obvykle dosahuje ukázáním těžkosti výrokových formulí kódujících superpolynomiální spodní odhady pro booleovské obvody. Nejprve prezentujeme několik známých technik a tvrzení. Přirozené důkazy, efektívní interpolaci, KPT větu, iterovatelnost, gadget generátory atd. Pak dokážem několik původních výsledků. Ukážeme nedokazatelnost superpolynomiálních spodních odhadů na booleovské obvody v systémech s efektívní interpolaci (modulo složitostní předpoklad) a v systémech podobajících se stromovým Frege systémům manipulujícím s formulemi, které obsahují jen málo proměnných dokazovaného tvrzení. Tyto výsledky jsou založeny na dokazování těžkosti Nisan-Wigdersonových generátorů v príslušných důkazových systémech.
|
|
| |
|
|
Deniable encryption
Šebek, Marcel ; Tůma, Jiří (vedoucí práce) ; Krajíček, Jan (oponent)
V práci studujeme popiratelné šifrování, které navrhli Canetti et al. (CRYP- TO 1997). Běžná šifrovací schémata zaručují dobrou úroveň bezpečnosti, avšak pokud může útočník přinutit odesílatele a/nebo příjemce zprávy k odtajnění svých neveřejných informací, tato schémata selhávají. Pokud útočník zná správ- ný šifrový text, tajné vstupy ve většině případů zavazují uživatele ke skutečnému otevřenému textu. Popiratelné šifrování poskytuje algoritmy, které umožní vyro- bit alternativní tajnou informaci, jež útočníka přesvědčí o tom, že byl zašifrován jiný otevřený text. Obsahem práce je představení nejdůležitějších výsledků v této oblasti, kon- krétně schemata autorů Canetti et al. (CRYPTO 1997), schema autorů Klo- nowski et al. (SOFSEM 2008) založené na šifře ElGamal a schémata a negativ- ní výsledek autorů Bendlin et al. (ASIACRYPT 2011). Kromě studia známých výsledků a jejich prezentace v jednotném prostředí podrobně zkoumáme sché- mata založená na simulovatelném šifrování. Zkonstruujeme schéma, které je bi- popiratelné, a jehož obě indukovaná schémata jsou popiratelná příjemcem (ve flexibilním/vícedistribučním smyslu). Dále vyvracíme správnost konstrukce plně bipopiratelného schématu autorů Bendlin et al. (ASIACRYPT 2011) a tento vý- sledek ověříme počítačovou simulací. Tím se konstrukce tohoto typu schématu...
|
|
|
Problém spektra
Poláková, Kristýna ; Krajíček, Jan (vedoucí práce) ; Jeřábek, Emil (oponent)
V této práci studujeme problém spektra, který předložil v roce 1952 H. Scholz. Definujeme základní pojmy, které s tímto problémem souvisí. Sledujeme jeho další vývoj a především souvislosti s množinami z třídy výpočetní složitosti NE. Definujeme zobecněná spektra. Představíme příklady množin přirozených čísel, která jsou spektra.
|
|
| |
|
|
Komunikační složitost
Wagner, Vojtěch ; Krajíček, Jan (vedoucí práce) ; Koucký, Michal (oponent)
Název práce: Komunikační složitost Autor: Vojtěch Wagner Katedra: Katedra algebry Vedoucí bakalářské práce: prof. RNDr. Jan Krajíček, DrSc. Abstrakt: Práce se zabývá teorií komunikační složitosti, která uvažuje model dvou (popř. více) hráčů, každý z nich vlastní binární vstup (x, resp. y), o němž má informaci pouze on sám. Jejich společným cílem je spočítat hodnotu něja- ké funkce f(x, y) na daných vstupech. Komunikační složitost pak měří množství informace vyměněné mezi hráči při jejich snaze spočítat f(x, y). Práce zkoumá především dva hlavní modely - deterministický model, v němž je rozhodování hráčů vždy jednoznačné a hráči spočítají vždy správnou hodnotu a pravděpo- dobnostní přístup, ve kterém je povolena náhodnost a snahou hráčů je spočítat hodnotu f(x, y) s dostatečně velkou pravděpodobností. Jsou uvedeny základní pojmy modelů a metody spodních odhadů pro dokazování komunikační složitosti funkcí. Vše je ilustrováno na příkladech několika základních funkcí. Další část je věnována příkladům náročnějším a v praxi použitelným, u nichž je řešena otázka jejich komunikačí složitosti jak deterministické, tak pravděpodobnostní. Klíčová slova: komunikační složitost, deterministický model, pravděpodobnost- ní model, spodní odhady komunikační složitosti. 1
|
|
| |
host ::
RSS.