|
|
Těžké tautologie
Pich, Ján ; Krajíček, Jan (advisor) ; Pudlák, Pavel (referee)
We investigate the unprovability of NP$\not\subseteq$P/poly in various fragments of arithmetic. The unprovability is usually obtained by showing hardness of propositional formulas encoding superpolynomial circuit lower bounds. Firstly, we discuss few relevant techniques and known theorems. Namely, natural proofs, feasible interpolation, KPT theorem, iterability, gadget generators etc. Then we prove some original results. We show the unprovability of superpolynomial circuit lower bounds for systems admitting certain forms of feasible interpolation (modulo a hardness assumption) and for systems roughly described as tree-like Frege systems working with formulas using only a small fraction of variables of the statement that is supposed to be proved. These results are obtained by proving the hardness of the Nisan-Wigderson generators in corresponding proof systems.
|
|
| |
|
|
Legal regulation of the environmental impact assessment
Pich, Jan ; Sobotka, Michal (advisor) ; Humlíčková, Petra (referee)
Environmental Impact Assessment is one of internationally recognised tools providing environmental protection. Purpose of the assessment is to identify and comprehensively evaluate environmental impact of a project with participation of the public, professionals and administrative bodies, prior to the realisation of the project. Information gained through this process is then used as a basis for decision making in procedures granting development or other consents. The thesis aims to analyse in particular the Czech environmental impact assessment law with emphasis on its recent amendment and reasons of its implementation.
|
|
|
Legal regulation of the environmental impact assessment
Pich, Jan ; Sobotka, Michal (advisor) ; Humlíčková, Petra (referee)
Environmental Impact Assessment is one of internationally recognised tools providing environmental protection. Purpose of the assessment is to identify and comprehensively evaluate environmental impact of a project with participation of the public, professionals and administrative bodies, prior to the realisation of the project. Information gained through this process is then used as a basis for decision making in procedures granting development or other consents. The thesis aims to analyse in particular the Czech environmental impact assessment law with emphasis on its recent amendment and reasons of its implementation.
|
|
|
Complexity theory in Feasible Mathematics
Pich, Ján ; Krajíček, Jan (advisor) ; Pudlák, Pavel (referee) ; Buss, Samuel (referee)
Title: Complexity Theory in Feasible Mathematics Author: Ján Pich Department: Department of Algebra Supervisor: Prof. RNDr. Jan Krajíček, DrSc., MAE Abstract: We study the provability of statements and conjectures from Complex- ity Theory in Bounded Arithmetic. First, modulo a hardness assumption, we show that theories weaker in terms of provably total functions than Buss's theory S1 2 cannot prove nk -size circuit lower bounds for SAT formalized as a Σb 2-formula LB(SAT, nk ). In particular, the true universal first-order theory in the language containing names for all uniform NC1 algorithms denoted TNC1 does not prove LB(SAT, n4kc ) where k ≥ 1, c ≥ 2 unless each function f ∈ SIZE(nk ) can be approximated by formulas Fn of subexponential size 2O(n1/c) with subexponential advantage: Px∈{0,1}n [Fn(x) = f(x)] ≥ 1/2 + 1/2O(n1/c) . Unconditionally, V 0 does not prove quasipolynomial nlog n -size circuit lower bounds for SAT. Considering upper bounds, we prove the PCP theorem in Cook's theory PV1. This includes a formalization of the (n, d, λ)-graphs in PV1. A consequence of the result is that Extended Frege proof system admits p-size proofs of tautologies encoding the PCP theorem. Keywords: Circuit Lower Bounds, Bounded Arithmetic, The PCP theorem
|
|
|
Těžké tautologie
Pich, Ján ; Krajíček, Jan (advisor) ; Pudlák, Pavel (referee)
We investigate the unprovability of NP$\not\subseteq$P/poly in various fragments of arithmetic. The unprovability is usually obtained by showing hardness of propositional formulas encoding superpolynomial circuit lower bounds. Firstly, we discuss few relevant techniques and known theorems. Namely, natural proofs, feasible interpolation, KPT theorem, iterability, gadget generators etc. Then we prove some original results. We show the unprovability of superpolynomial circuit lower bounds for systems admitting certain forms of feasible interpolation (modulo a hardness assumption) and for systems roughly described as tree-like Frege systems working with formulas using only a small fraction of variables of the statement that is supposed to be proved. These results are obtained by proving the hardness of the Nisan-Wigderson generators in corresponding proof systems.
|
|
| |
guest ::
RSS feed.