Teorie, důkazy a výpočetní složitost

Poskytovatel
Akademie věd České republiky
Program
Granty výrazně badatelského charakteru zaměřené na oblast výzkumu rozvíjeného v současné době zejména v AV ČR
Veřejná soutěž
Výzkumné granty 4 (SAV02004-A)
Hlavní účastníci
—
Druh soutěže
VS - Veřejná soutěž
Číslo smlouvy
IAA1019401

Název projektu anglicky
Theories, proofs and computational complexity
Anotace anglicky
This is a purely tehoretical research in mathematics and theoretical computer science. The main aim is to study the concept of computational complexity from several points of view:1. first order tehories, 2. the propositional calculus and 3. voolean circuits. MOre specifically, we will study Bounded Arithmetic, the complexity of proofs in propositional calculus and various computational models. Furthermore, we shall investigate related questions in the foundations of mathematics and set theory.

Kategorie VaV
ZV - Základní výzkum
CEP - hlavní obor
BA - Obecná matematika
CEP - vedlejší obor
—
CEP - další vedlejší obor
—
OECD FORD - odpovídající obory <br>(dle <a href="http://www.vyzkum.cz/storage/att/E6EF7938F0E854BAE520AC119FB22E8D/Prevodnik_oboru_Frascati.pdf">převodníku</a>)
10101 - Pure mathematics

Hodnocení poskytovatelem
V - Vynikající výsledky projektu (s mezinárodním významem atd.)
Zhodnocení výsledků projektu
Byly dokázány věty o důkazové složitosti výrokového počtu, o teoriích omezené aritmetiky a složitosti booleovských obvodů. Byly nalezeny nové algoritmy pro on-line rozvrhování a analyzovali jsme jejich složitost.

Důvěrnost údajů
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Systémové označení dodávky dat
CEP09-AV0-IA-U/01:1
Datum dodání záznamu
2. 7. 2009

Podobné projekty(10)