Teorie Razborova a Rudiche a omezená aritmetika

• Název práce v češtině: Teorie Razborova a Rudiche a omezená aritmetika
• Název v anglickém jazyce: Razborov-Rudich theory and bounded arithmetic
• Akademický rok vypsání: 2008/2009
• Typ práce: bakalářská práce
• Jazyk práce: češ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í: 19.10.2008
• Datum zadání: 19.10.2008
• Datum a čas obhajoby: 29.06.2009 00:00
• Datum odevzdání elektronické podoby: 29.06.2009
• Datum proběhlé obhajoby: 29.06.2009
• Oponenti: Neil Thapen

Zásady pro vypracování

Nastudovat a presentovat teorii Razborova a Rudiche (tzv. natural proofs)
a její souvislost s nedokazatelností spodních odhadů pro Booleovské funkce
v omezené aritmetice.

Seznam odborné literatury

J.Krajíček, Bounded arithmetic, propositional logic, and complexity theory,
Encyclopedia of Mathematics and Its Applications, Vol.60, Cambridge University
Press, (1995).

J.Krajíček, Interpolation theorems, lower bounds for proof systems, and independence
results for bounded arithmetic, J. of Symbolic Logic, 62(2), (1997), str.457-486.

Alexander A. Razborov a Stephen Rudich, Natural proofs, in: Proc. of the 26th Annual
ACM Symposium on the Theory of Computing, (1994), 204-213.

Předběžná náplň práce

Práce se týká souvislostí matematické logiky a teorie výpočetní složitosti.

Předběžná náplň práce v anglickém jazyce

The project is concerned with connections between mathematical logic and
computational complexity theory.