Těžké tautologie
| Název práce v češtině: | Těžké tautologie |
|---|---|
| Název v anglickém jazyce: | Hard tautologies |
| Klíčová slova: | důkazová složitost, booleovské obvody, Nisan-Wigderson generátor |
| Klíčová slova anglicky: | proof complexity, circuit lower bounds, Nisan-Wigderson, generators |
| Akademický rok vypsání: | 2009/2010 |
| Typ práce: | diplomová práce |
| Jazyk práce: | angličtina |
| Ústav: | Katedra algebry (32-KA) |
| Vedoucí / školitel: | prof. RNDr. Jan Krajíček, DrSc. |
| Řešitel: | skrytý - zadáno a potvrzeno stud. odd. |
| Datum přihlášení: | 14.10.2009 |
| Datum zadání: | 14.10.2009 |
| Datum a čas obhajoby: | 26.05.2011 00:00 |
| Datum odevzdání elektronické podoby: | 07.04.2011 |
| Datum odevzdání tištěné podoby: | 15.04.2011 |
| Datum proběhlé obhajoby: | 26.05.2011 |
| Oponenti: | prof. RNDr. Pavel Pudlák, DrSc. |
| Zásady pro vypracování |
| Prostudovat známé konstrukce formulí obtížných pro
výrokové důkazové systémy a rozšířít některou z těchto konstrukcí na nový důkazový systém. Nebo navrhnout novou podobnou konstrukci. |
| Seznam odborné literatury |
| J.Krajíček, Dual weak pigeonhole principle, pseudo-surjective functions, and provability of circuit lower bounds , J. of Symbolic Logic, 69(1), (2004), pp.265-286.
J.Krajíček, "Bounded arithmetic, propositional logic, and complexity theory", Encyclopedia of Mathematics and Its Applications, Vol.60, Cambridge University Press,(1995). A.A.Razborov, Pseudorandom Generators Hard for k-DNF Resolution and Polynomial Calculus Resolution, preprint 2002-2003. |
| Předběžná náplň práce |
| Práce se dotýká jednoho ze základních problémů teorie složitosti. |
| Předběžná náplň práce v anglickém jazyce |
| The project concerns one of the basic problems of computational complexity. |