Arithmetic, proof theory and complexity theory

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
—
Main participants
Matematický ústav AV ČR, v. v. i.
Contest type
—
Contract ID
—

Project name in Czech
Aritmetika, teorie důkazů a teorie složitosti
Annotation in Czech
Toto je návrh základního výzkumu v teorii složitosti a v logických základech aritmetiky. Budeme pracovat na otevřených problémech v následujících oblastech: teorie složitosti, omezená aritmetika a výrokový počet, aritmetika vaššího řádu a teorie množin.Zvláště se zaměříme na následující problémy: spodní odhady pro komunikační složitost, vztah kryptografických hypotéz k aritmetice, tvrzení o nezávislosti pro omezenou aritmetiku, spodní odhady pro výrokový počet, modely alternativní teorie množin.

R&D category
—
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

Provider evaluation
V - Vynikající výsledky projektu (s mezinárodním významem atd.)
Project results evaluation
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í.

Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data delivery code
CEP/1999/AV0/AV09IA/V/3:3
Data delivery date
—

Similar projects(10)