All

What are you looking for?

All
Projects
Results
Organizations

Quick search

  • Projects supported by TA ČR
  • Excellent projects
  • Projects with the highest public support
  • Current projects

Smart search

  • That is how I find a specific +word
  • That is how I leave the -word out of the results
  • “That is how I can find the whole phrase”

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

    B - Running multi-year project

  • Latest support payment

    Mar 27, 2023

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

    CEP24-GA0-GA-R

  • Data delivery date

    Feb 19, 2024

Finance

  • Total approved costs

    10,913 thou. CZK

  • Public financial support

    10,664 thou. CZK

  • Other public sources

    249 thou. CZK

  • Non public and foreign sources

    0 thou. CZK