Těžké tautologie
| Thesis title in Czech: | Těžké tautologie |
|---|---|
| Thesis title in English: | Hard tautologies |
| Key words: | důkazová složitost, booleovské obvody, Nisan-Wigderson generátor |
| English key words: | proof complexity, circuit lower bounds, Nisan-Wigderson, generators |
| Academic year of topic announcement: | 2009/2010 |
| Thesis type: | diploma thesis |
| Thesis language: | angličtina |
| Department: | Department of Algebra (32-KA) |
| Supervisor: | prof. RNDr. Jan Krajíček, DrSc. |
| Author: | hidden - assigned and confirmed by the Study Dept. |
| Date of registration: | 14.10.2009 |
| Date of assignment: | 14.10.2009 |
| Date and time of defence: | 26.05.2011 00:00 |
| Date of electronic submission: | 07.04.2011 |
| Date of submission of printed version: | 15.04.2011 |
| Date of proceeded defence: | 26.05.2011 |
| Opponents: | prof. RNDr. Pavel Pudlák, DrSc. |
| Guidelines |
| 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. |
| References |
| 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. |
| Preliminary scope of work |
| Práce se dotýká jednoho ze základních problémů teorie složitosti. |
| Preliminary scope of work in English |
| The project concerns one of the basic problems of computational complexity. |