Computational models and complexity of computations
Project goals
A basic research project in informatics whose main aim is to contribute further to the development of the computational complexity theory.It is centered around various universal and restricted computational models whose computational and descriptional power and efficiency will be studied.The respective research will proceed along two main research lines: -investigation of computational complexity within classical computational paradigms of sequential computing , represented by Turing machines , RAMs,Boolean circuits branching programs, etc. - computational complexity studied within the framework of recent pradigms of parallel computing, neurocomputing, genetic computing, cognitive computing, etc. The proposed research team consists from 5 key researchers complemented by their 5 PhD students.
Keywords
Public support
Provider
Czech Science Foundation
Programme
Standard projects
Call for proposals
—
Main participants
Ústav informatiky AV ČR, v. v. i.
Contest type
—
Contract ID
—
Alternative language
Project name in Czech
Výpočetní modely a složitost výpočtů
Annotation in Czech
Jde o projekt základního výzkumu v informatice, jehož cílem je přispět k rozvoji teorie výpočetní složitosti. Soustřeďuje se na různé univerzální i omezené výpočetní modely, kde zkoumá jejich výpočetní a deskriptivní sílu a efektivitu. Výzkum bude probíhat ve dvou vzájemně se doplňujících liniích: - výzkum výpočetní složitosti v rámci klasických výpočetních paradigmat, representovaných Turingovými stroji, RAMy, booleovskými obvody, větvícími se programy, apod. - výpočetní složitost v rámci nových paradigmat paralelních výpočtů, neurovýpočtů, genetických výpočtů, analogových výpočtů, apod. Projekt volně navazuje na předchozí projekt GAČR (1995-1997). Účastní se ho 5 klíčových pracovníků a 5 doktorandů.
Scientific branches
Completed project evaluation
Provider evaluation
V - Vynikající výsledky projektu (s mezinárodním významem atd.)
Project results evaluation
Přínosem řešitelského kolektivu jsou jednak průkopnické práce přinášející nové modely výpočtů (J. Wiedermann), které získali významný publikační a prezentační prostor, jednak řadu technických výsledků, které mají značný stupeň obtížnosti (Savický, Šíma,
Solution timeline
Realization period - beginning
Jan 1, 1998
Realization period - end
Jan 1, 2000
Project status
U - Finished project
Latest support payment
—
Data delivery to CEP
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data delivery code
CEP/2001/GA0/GA01GA/U/N/9:4
Data delivery date
—
Finance
Total approved costs
2,166 thou. CZK
Public financial support
1,295 thou. CZK
Other public sources
0 thou. CZK
Non public and foreign sources
0 thou. CZK
Basic information
Recognised costs
2 166 CZK thou.
Public support
1 295 CZK thou.
59%
Provider
Czech Science Foundation
CEP
BA - General mathematics
Solution period
01. 01. 1998 - 01. 01. 2000