|
|
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.
|
|
| |
|
|
Právní úprava posuzování vlivů na životní prostředí
Pich, Jan ; Sobotka, Michal (vedoucí práce) ; Humlíčková, Petra (oponent)
Proces posuzování vlivů záměrů na životní prostředí je jedním z mezinárodně uznávaných nástrojů zajišťující ochranu životního prostředí. Účelem posouzení je získání poznatků o vlivech záměru a jejich komplexní vyhodnocení za účasti veřejnosti, odborníků a orgánů státní správy dříve, než je přistoupeno k realizaci záměru. Tímto postupem získané informace jsou následně využívány jako poklad pro řízení, ve kterých se rozhoduje o povolení záměru. Tato práce si klade za cíl rozebrat zejména českou právní úpravu tohoto procesu s důrazem na její současnou novelizaci a důvody, které k ní vedly.
|
|
|
Právní úprava posuzování vlivů na životní prostředí
Pich, Jan ; Sobotka, Michal (vedoucí práce) ; Humlíčková, Petra (oponent)
Proces posuzování vlivů záměrů na životní prostředí je jedním z mezinárodně uznávaných nástrojů zajišťující ochranu životního prostředí. Účelem posouzení je získání poznatků o vlivech záměru a jejich komplexní vyhodnocení za účasti veřejnosti, odborníků a orgánů státní správy dříve, než je přistoupeno k realizaci záměru. Tímto postupem získané informace jsou následně využívány jako poklad pro řízení, ve kterých se rozhoduje o povolení záměru. Tato práce si klade za cíl rozebrat zejména českou právní úpravu tohoto procesu s důrazem na její současnou novelizaci a důvody, které k ní vedly.
|
|
|
Complexity theory in Feasible Mathematics
Pich, Ján ; Krajíček, Jan (vedoucí práce) ; Pudlák, Pavel (oponent) ; Buss, Samuel (oponent)
Skúmame dokázateľnosť tvrdení z teórie zložitosti v obmedzenej aritmetike. Za istých zložitostných predpokladov ukážeme, že teórie so slabšími dosvedčovacími vlastnosťami než $S^1_2$ nemôžu dokázať spodné odhady veľkosti $n^k$ na booleovské obvody pre SAT vyjadrené formulou $LB(SAT,n^k)$. Špeciálne, prvorádová teória pravdivých univerzálnych tvrdení v jazyku obsahujúcom symboly pre všetky uniformné $NC^1$ algoritmy nedokazuje $LB(SAT,n^{4kc})$ pre $k\geq 1,c\geq 2$ predpokladajúc existenciu funkcie $f\in SIZE(n^k)$, ktorá nie je aproximovateľná formulami $F_n$ subexponenciálnej veľkosti $2^{O(n^{1/c})}$ so subexponenciálnou výhodou: $P_{x\in\{0,1\}^n}[F_n(x)=f(x)]\geq 1/2+1/2^{O(n^{1/c})}$. Bezpodmienečne, teória $V^0$ nedokazuje kvazipolynomiálne spodné odhady na booleovské obvody pre SAT. Čo sa týka horných odhadov, dokážeme PCP vetu v Cookovej teórii $PV_1$. To zahŕňa formalizáciu $(n,d,\lambda)$-grafov v $PV_1$. Ako dôsledok dostaneme polynomiálne krátke Extended Frege dôkazy tautologií vyjdadrujúcich PCP vetu. Powered by TCPDF (www.tcpdf.org)
|
|
|
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.
|
|
| |
host ::
RSS.