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.
Seznam odborné literatury
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.
- zadáno a potvrzeno stud. odd.