Matematická logika a výpočetní složitost
Cíle projektu
Plánujeme pracovat v následujících souvisejících oblastech: složitost výrokových kalkulů, omezená aritmetika, obvodová složitost, komunikační složitost, efektivní algoritmy, on-line algoritmy, aritmetika vyššího řádu a teorie množin a teorie modelů těles. Tyto oblasti se jak překrývají ve výsledcích, tak používjí stejné či podobné metody. Hlavní cíl je získat lepší porozumění pro fenomén složitosti. Výstupem budou vědecké publikace v kvalitních časopisech a sbornících konferencí.
Klíčová slova
bounded arithmeticset theorycomputational complexityproof complexity
Veřejná podpora
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ěž
—
Hlavní účastníci
Matematický ústav AV ČR, v. v. i.
Druh soutěže
VS - Veřejná soutěž
Číslo smlouvy
—
Alternativní jazyk
Název projektu anglicky
Mathematical logic and computational complexity
Anotace anglicky
We plan to work in the following related areas: the complexity of propositional calculus, bounded arithmetic, circuit complexity, communication complexity, efficient algorithms, on-line algorithms, higher-order arithmetic and set theory, and model theoryof fields. The areas both overlap in results and use same or similar methods. The main aim is to gain better understanding of the phenomenon of complexity. The output will be scientific publications.
Vědní obory
Kategorie VaV
—
CEP - hlavní obor
BA - Obecná matematika
CEP - vedlejší obor
—
CEP - další vedlejší obor
—
OECD FORD - odpovídající obory
(dle převodníku)10101 - Pure mathematics
Hodnocení dokončeného projektu
Hodnocení poskytovatelem
V - Vynikající výsledky projektu (s mezinárodním významem atd.)
Zhodnocení výsledků projektu
Výsledky se týkají komunikační složitosti, složitosti obvodů, složitosti výrokových důkazů, konservativnosti v omezené aritmetice, kombinatorických vlastností definovatelných množin, extremálních úloh v kombinatorice a aproximačních a on-line algoritmů
Termíny řešení
Zahájení řešení
1. 1. 1999
Ukončení řešení
1. 1. 2003
Poslední stav řešení
U - Ukončený projekt
Poslední uvolnění podpory
—
Dodání dat do CEP
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
CEP/2004/AV0/AV04IA/U/N/3:2
Datum dodání záznamu
13. 10. 2004
Finance
Celkové uznané náklady
4 576 tis. Kč
Výše podpory ze státního rozpočtu
1 696 tis. Kč
Ostatní veřejné zdroje financování
2 880 tis. Kč
Neveřejné tuz. a zahr. zdroje finan.
0 tis. Kč
Uznané náklady
4 576 tis. Kč
Statní podpora
1 696 tis. Kč
0%
Poskytovatel
Akademie věd České republiky
CEP
BA - Obecná matematika
Doba řešení
01. 01. 1999 - 01. 01. 2003