Mathematical logic and computational complexity
Project goals
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.
Keywords
bounded arithmeticset theorycomputational complexityproof complexity
Public support
Provider
Academy of Sciences of the Czech Republic
Programme
Grants of distinctly investigative character focused on the sphere of research pursued at present particularly in the Academy of Sciences of the Czech Republic
Call for proposals
—
Main participants
Matematický ústav AV ČR, v. v. i.
Contest type
VS - Public tender
Contract ID
—
Alternative language
Project name in Czech
Matematická logika a výpočetní složitost
Annotation in Czech
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í.
Scientific branches
Completed project evaluation
Provider evaluation
V - Vynikající výsledky projektu (s mezinárodním významem atd.)
Project results evaluation
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ů
Solution timeline
Realization period - beginning
Jan 1, 1999
Realization period - end
Jan 1, 2003
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/2004/AV0/AV04IA/U/N/3:2
Data delivery date
Oct 13, 2004
Finance
Total approved costs
4,576 thou. CZK
Public financial support
1,696 thou. CZK
Other public sources
2,880 thou. CZK
Non public and foreign sources
0 thou. CZK
Recognised costs
4 576 CZK thou.
Public support
1 696 CZK thou.
0%
Provider
Academy of Sciences of the Czech Republic
CEP
BA - General mathematics
Solution period
01. 01. 1999 - 01. 01. 2003