Theories, proofs and computational complexity
Project goals
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.
Keywords
logicpropositional calculuscomputational complexityset theory
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
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
Recognised costs
2 165 CZK thou.
Public support
2 165 CZK thou.
0%
Provider
Academy of Sciences of the Czech Republic
CEP
BA - General mathematics
Solution period
01. 01. 2004 - 31. 12. 2008