Complexity of mathematical proofs and structures
Project goals
We study weak logical systems, guided by the question: what is the weakest natural theory in which we can prove a mathematical statement? This question is often fundamentally complexity theoretic in nature, as proofs in such weak systems can be associated with feasible computations. We will study this and related topics in a range of settings, including bounded arithmetic, model theory, algebraic complexity, bounded set theory, and nonclassical logics.
Keywords
logicproof complexitymodel theorybounded arithmeticcomputational complexityalgebraic complexitypropositional translationsweak set theorymodal logic
Public support
Provider
Czech Science Foundation
Programme
Standard projects
Call for proposals
Standardní projekty 23 (SGA0201900001)
Main participants
Matematický ústav AV ČR, v. v. i.
Contest type
VS - Public tender
Contract ID
19-05497S
Alternative language
Project name in Czech
Složitost matematických důkazů a struktur
Annotation in Czech
Budeme studovat logické systémy se zřetelem na otázku, jaká je nejslabší přirozená teorie, v níž lze dokázat dané matematické tvrzení. Tato otázka se často v hloubi týká výpočetní složitosti, neboť důkazy v takovýchto slabých systémech souvisí s efektivními výpočty. Budeme studovat tyto a příbuzná témata v různých kontextech, mj. v omezené aritmetice, teorii modelů, algebraické složitosti, omezené teorii množin a neklasických logikách.
Scientific branches
Completed project evaluation
Provider evaluation
U - Uspěl podle zadání (s publikovanými či patentovanými výsledky atd.)
Project results evaluation
The project has led to a large number of results within theoretical computer science (9 conference and 9 journal papers), particularly in logic and proof complexity; particular highlights of the project include results concerning challenging lower bound problems and related techniques in mathematical logic.
Solution timeline
Realization period - beginning
Jan 1, 2019
Realization period - end
Jun 30, 2022
Project status
U - Finished project
Latest support payment
Apr 1, 2022
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
CEP23-GA0-GA-U
Data delivery date
Jun 26, 2023
Finance
Total approved costs
9,171 thou. CZK
Public financial support
8,514 thou. CZK
Other public sources
657 thou. CZK
Non public and foreign sources
0 thou. CZK
Basic information
Recognised costs
9 171 CZK thou.
Public support
8 514 CZK thou.
92%
Provider
Czech Science Foundation
OECD FORD
Pure mathematics
Solution period
01. 01. 2019 - 30. 06. 2022