Theories, proofs and computational 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
Výzkumné granty 4 (SAV02004-A)
Main participants
—
Contest type
VS - Public tender
Contract ID
IAA1019401
Alternative language
Project name in Czech
Teorie, důkazy a výpočetní složitost
Annotation in Czech
Jedná se o teoretický výzkum v matematice a teoretické informatice. Hlavním cílem je studovat pojem výpočetní složitosti z několika hledisek: 1. teorii prvního řádu, 2. výrokového počtu a 3. booleovských obvodů. Konkrétně se jedná o studium omezené aritmetiky, složitosti důkazů ve výrokovém počtu a různých výpočetních modelů. Budeme zkoumat také související otázky logických základů matematiky a teorie množin.
Scientific branches
R&D category
ZV - Basic research
CEP classification - main branch
BA - General mathematics
CEP - secondary branch
—
CEP - another secondary branch
—
OECD FORD - equivalent branches <br>(according to the <a href="http://www.vyzkum.cz/storage/att/E6EF7938F0E854BAE520AC119FB22E8D/Prevodnik_oboru_Frascati.pdf">converter</a>)
10101 - Pure mathematics
Completed project evaluation
Provider evaluation
V - Vynikající výsledky projektu (s mezinárodním významem atd.)
Project results evaluation
Theorems about proof complexity of the propositional calculus, about bounded arithmetic theories and about the complexity of boolean circuits were proved. New algorithms for on-line scheduling and analyzed their complexity were found.
Solution timeline
Realization period - beginning
Jan 1, 2004
Realization period - end
Dec 31, 2008
Project status
U - Finished project
Latest support payment
Feb 21, 2008
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
CEP09-AV0-IA-U/01:1
Data delivery date
Jul 2, 2009
Finance
Total approved costs
2,165 thou. CZK
Public financial support
2,165 thou. CZK
Other public sources
0 thou. CZK
Non public and foreign sources
0 thou. CZK