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.
| Identifer | oai:union.ndltd.org:nusl.cz/oai:invenio.nusl.cz:300133 |
| Date | January 2011 |
| Creators | Pich, Ján |
| Contributors | Krajíček, Jan, Pudlák, Pavel |
| Source Sets | Czech ETDs |
| Language | English |
| Detected Language | English |
| Type | info:eu-repo/semantics/masterThesis |
| Rights | info:eu-repo/semantics/restrictedAccess |
Page generated in 0.0015 seconds