Logic and unsatisfiability
Public support
Provider
Czech Science Foundation
Programme
Standard projects
Call for proposals
SGA0202300001
Main participants
Matematický ústav AV ČR, v. v. i.
Contest type
VS - Public tender
Contract ID
23-04825S
Alternative language
Project name in Czech
Logika a nesplnitelnost
Annotation in Czech
Jak se mění délka nejkratšího důkazu daného tvrzení, když zvětšujeme složitost pojmů, jež lze v důkazu použít? Tato základní otázka logiky je pro důkazy ve slabých teoriích nebo ve výrokové logice úzce svázaná s obtížnými fundamentálními problémy výpočetní složitosti. Konkrétně, tvrzení NP/=coNP je ekvivalentní neexistenci výrokového důkazového systému, v němž mají všechny tautologie krátké důkazy. Varianty této otázky budeme studovat v rozličných důkazových systémech, které mají často kombinatorický či algebraický charakter, nebo pochází z certifikátů nesplnitelnosti dané formule produkovaných praktickými SAT algoritmy. Chceme pochopit obecnější způsoby uvažování, jež tyto systémy umožňují, v kontextu teorií prvního řádu. Cílem je získat vhled do otázek, jaké typy tvrzení je těžké nebo snadné dokázat a jaké jsou vztahy mezi důkazovými systémy. Předpokladem k této práci je hlubší porozumění schopnosti slabých logických teorií dokazovat základní matematická tvrzení.
Scientific branches
R&D category
ZV - Basic research
OECD FORD - main branch
10101 - Pure mathematics
OECD FORD - secondary branch
—
OECD FORD - another secondary branch
—
CEP - equivalent branches <br>(according to the <a href="http://www.vyzkum.cz/storage/att/E6EF7938F0E854BAE520AC119FB22E8D/Prevodnik_oboru_Frascati.pdf">converter</a>)
BA - General mathematics
Solution timeline
Realization period - beginning
Jan 1, 2023
Realization period - end
Dec 31, 2025
Project status
Z - Beginning multi-year project
Latest support payment
—
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-R
Data delivery date
Mar 17, 2023
Finance
Total approved costs
11,201 thou. CZK
Public financial support
10,952 thou. CZK
Other public sources
249 thou. CZK
Non public and foreign sources
0 thou. CZK