Aritmetika, teorie důkazů a teorie složitosti

Poskytovatel
Akademie věd České republiky
Program
Granty výrazně badatelského charakteru zaměřené na oblast výzkumu rozvíjeného v současné době zejména v AV ČR
Veřejná soutěž
—
Hlavní účastníci
Matematický ústav AV ČR, v. v. i.
Druh soutěže
—
Číslo smlouvy
—

Název projektu anglicky
Arithmetic, proof theory and complexity theory
Anotace anglicky
This is a project of basic research in complexity theory and logical foundations of arithmetic. We plan to work on open problems in the following areas: complexity theory, bounded arithmetic and propositional logic, higher order arithmetic and propositional logic, higher order arithmetic and set theory. Problems of particular interest are: lower bounds for communication complexity, relation of cryptogrphical conjectures to arithmetic, independence results for bounded arithmetic, lower bounds for propositional pr. system, models of alternative set theory.

Kategorie VaV
—
CEP - hlavní obor
BA - Obecná matematika
CEP - vedlejší obor
—
CEP - další vedlejší obor
—
OECD FORD - odpovídající obory <br>(dle <a href="http://www.vyzkum.cz/storage/att/E6EF7938F0E854BAE520AC119FB22E8D/Prevodnik_oboru_Frascati.pdf">převodníku</a>)
10101 - Pure mathematics

Hodnocení poskytovatelem
V - Vynikající výsledky projektu (s mezinárodním významem atd.)
Zhodnocení výsledků projektu
Byly získány dolní odhady na složitost bool. obvodů a dolní odhady na délku důkazů ve výrokovém počtu, výsledky o teoriích 1.řádu, tzv. omezených aritmetikách, a řada výsledků o algoritmech na rozvrhování a splňování bool. formulí.

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
CEP/1999/AV0/AV09IA/V/3:3
Datum dodání záznamu
—

Podobné projekty(10)