Složitost matematických důkazů a struktur
Cíle projektu
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.
Klíčová slova
logicproof complexitymodel theorybounded arithmeticcomputational complexityalgebraic complexitypropositional translationsweak set theorymodal logic
Veřejná podpora
Poskytovatel
Grantová agentura České republiky
Program
Standardní projekty
Veřejná soutěž
Standardní projekty 23 (SGA0201900001)
Hlavní účastníci
Matematický ústav AV ČR, v. v. i.
Druh soutěže
VS - Veřejná soutěž
Číslo smlouvy
19-05497S
Alternativní jazyk
Název projektu anglicky
Complexity of mathematical proofs and structures
Anotace anglicky
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.
Vědní obory
Kategorie VaV
ZV - Základní výzkum
OECD FORD - hlavní obor
10101 - Pure mathematics
OECD FORD - vedlejší obor
—
OECD FORD - další vedlejší obor
—
CEP - odpovídající obory
(dle převodníku)BA - Obecná matematika
Hodnocení dokončeného projektu
Hodnocení poskytovatelem
U - Uspěl podle zadání (s publikovanými či patentovanými výsledky atd.)
Zhodnocení výsledků projektu
Projekt vyústil ve značné množství výsledků v teoretické informatice, specificky v logice a složitosti důkazů (9 konferenčních a 9 časopiseckých publikací); nejvýznamnější výsledky projektu se týkají obtížných problémů souvisejících s dolními odhady ve složitosti důkazů včetně souvisejících metod z matematické logiky.
Termíny řešení
Zahájení řešení
1. 1. 2019
Ukončení řešení
30. 6. 2022
Poslední stav řešení
U - Ukončený projekt
Poslední uvolnění podpory
1. 4. 2022
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
CEP23-GA0-GA-U
Datum dodání záznamu
26. 6. 2023
Finance
Celkové uznané náklady
9 171 tis. Kč
Výše podpory ze státního rozpočtu
8 514 tis. Kč
Ostatní veřejné zdroje financování
657 tis. Kč
Neveřejné tuz. a zahr. zdroje finan.
0 tis. Kč
Uznané náklady
9 171 tis. Kč
Statní podpora
8 514 tis. Kč
0%
Poskytovatel
Grantová agentura České republiky
OECD FORD
Pure mathematics
Doba řešení
01. 01. 2019 - 30. 06. 2022