Student-teacher computations and search problems

• Thesis title in Czech: Student-teacher computations and search problems
• Thesis title in English: Student-teacher computations and search problems
• Key words: dosvědčovací věty|interaktivní výpočet|vyhledávací problémy
• English key words: witnessing theorems|interactive computation|search problems
• Academic year of topic announcement: 2023/2024
• 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: 13.12.2023
• Date of assignment: 14.12.2023
• Confirmed by Study dept. on: 14.12.2023
• Date of electronic submission: 17.07.2025

Guidelines

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.

References

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.

Preliminary scope of work in English

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).