Teorie Razborova a Rudiche a omezená aritmetika

• Thesis title in Czech: Teorie Razborova a Rudiche a omezená aritmetika
• Thesis title in English: Razborov-Rudich theory and bounded arithmetic
• Academic year of topic announcement: 2008/2009
• Thesis type: Bachelor's thesis
• Thesis language: češ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: 19.10.2008
• Date of assignment: 19.10.2008
• Date and time of defence: 29.06.2009 00:00
• Date of electronic submission: 29.06.2009
• Date of proceeded defence: 29.06.2009
• Opponents: Neil Thapen

Guidelines

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

References

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.

Preliminary scope of work

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

Preliminary scope of work in English

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