Student-teacher computations and search problems
| Název práce v češtině: | Student-teacher computations and search problems |
|---|---|
| Název v anglickém jazyce: | Student-teacher computations and search problems |
| Klíčová slova: | interactive computation|search problems |
| Klíčová slova anglicky: | interactive computation|search problems |
| Akademický rok vypsání: | 2023/2024 |
| Typ práce: | diplomová práce |
| Jazyk práce: | |
| Ú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í: | 13.12.2023 |
| Datum zadání: | 14.12.2023 |
| Datum potvrzení stud. oddělením: | 14.12.2023 |
| Zásady pro vypracování |
| The task is to find interesting examples of S-T computations and possibly prove new upper or lower bounds
on the number of rounds in the relativized setting. The thesis will be written in English. |
| Seznam odborné literatury |
| J.Krajicek, P.Pudlak and J.Sgall, Interactive Computations of Optimal Solutions,
in: B. Rovan (ed.): Mathematical Foundations of Computer Science} (B. Bystrica, August '90), LN in Computer Science 452, Springer-Verlag, (1990), pp.48-60. |
| Předběžná náplň práce v anglickém jazyce |
| The S-T computations model a particular way how one can witness in an interactive manner the truth of a UEU-sentence in a structure.
The computation proceeds in rounds and the main measure of complexity of the search problem (i.e. the witnessing task) is the number of rounds. This model relates to mathematical logic (e.g. Herbrand-type theorems) and to computational complexity (e.g. optimization problems or Sigma-2 search problems). |