hidden - assigned and confirmed by the Study Dept.
Date of registration:
09.04.2014
Date of assignment:
10.04.2014
Confirmed by Study dept. on:
04.06.2014
Date and time of defence:
16.06.2016 00:00
Date of electronic submission:
11.05.2016
Date of submission of printed version:
13.05.2016
Date of proceeded defence:
16.06.2016
Opponents:
Neil Thapen
Guidelines
Blum, Shub and Smale generalized the Turing machine model so that it can hold at a unit cost an element of a fixed structure and can compute in a unit time the basic operations and relations of the structure. The aim of the project is to see if and how basic notions and constructions of complexity theory underlying cryptigraphy (e.g. one-way functions or pseudorandom generators) can be transferred to this set-up.
Blumová, Shub a Smale zobecnili model Turingova stroje tak, že může v jednotce paměti držet prvek libovolné pevné struktury a počítat její základní operace a relace v jednotce času. Cílem projektu je prozkoumat, jak se do tohoto modelu dají přenést základní pojmy a konstrukce teorie složitosti (např. jednosměrné funkce či pseudonáhodné generátory), které jsou v základech kryptografie.
References
L.Blum, M.Shub a S.Smale, "On a Theory of Computation and Complexity over the Real Numbers: NP-completeness, Recursive Functions and Universal Machines", Bull. AMS 21(1),
(1989), str.1-46.
L.Blum, F.Cucker, M.Shub a S.Smale, "Complexity and Real Computation", Springer, 1997.
- assigned and confirmed by the Study Dept.