Models of bounded arithmetic
| Název práce v češtině: | Modely omezené aritmetiky |
|---|---|
| Název v anglickém jazyce: | Models of bounded arithmetic |
| Klíčová slova: | omezená aritmetika|teorie modelů |
| Klíčová slova anglicky: | bounded arithmetic|model theory |
| Akademický rok vypsání: | 2020/2021 |
| 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í: | 05.03.2021 |
| Datum zadání: | 05.03.2021 |
| Datum potvrzení stud. oddělením: | 09.03.2021 |
| Datum a čas obhajoby: | 14.06.2022 09:00 |
| Datum odevzdání elektronické podoby: | 04.05.2022 |
| Datum odevzdání tištěné podoby: | 09.05.2022 |
| Datum proběhlé obhajoby: | 14.06.2022 |
| Oponenti: | doc. Mgr. Jan Šaroch, Ph.D. |
| Zásady pro vypracování |
| Bounded arithmetic theories are logical counterparts of computational complexity classes.
Constructions of their models relate to various computational and proof complexity problems. The task is to perform an example of such a construction. |
| Seznam odborné literatury |
|
M.Ajtai, The complexity of the pigeonhole principle, Proc. IEEE 29th Annual Symp. on Foundation of Computer Science, (1988), pp. 346-355. viz tez: https://www2.karlin.mff.cuni.cz/~krajicek/ajtai94.pdf J.Krajicek, Bounded arithmetic, propositional logic, and complexity theory, Cambridge University Press, Cambridge - New York - Melbourne, (1995). [Sec.12.7] J.Krajicek, Forcing with random variables and proof complexity, Cambridge University Press, Cambridge - New York - Melbourne, (2011). J.Krajicek, Proof Complexity, Cambridge U. Press, (2019). [Chpt.20 there] |
| Předběžná náplň práce |
| A relation between logic and complexity theory. |
| Předběžná náplň práce v anglickém jazyce |
| A relation between logic and complexity theory. |