Vše

Co hledáte?

Vše
Projekty
Výsledky výzkumu
Subjekty

Rychlé hledání

  • Projekty podpořené TA ČR
  • Významné projekty
  • Projekty s nejvyšší státní podporou
  • Aktuálně běžící projekty

Chytré vyhledávání

  • Takto najdu konkrétní +slovo
  • Takto z výsledků -slovo zcela vynechám
  • “Takto můžu najít celou frázi”

Logika a nesplnitelnost

Veřejná podpora

  • Poskytovatel

    Grantová agentura České republiky

  • Program

    Standardní projekty

  • Veřejná soutěž

    SGA0202300001

  • Hlavní účastníci

    Matematický ústav AV ČR, v. v. i.

  • Druh soutěže

    VS - Veřejná soutěž

  • Číslo smlouvy

    23-04825S

Alternativní jazyk

  • Název projektu anglicky

    Logic and unsatisfiability

  • Anotace anglicky

    How does the size of the smallest proof of a statement change, as we increase the complexity of the concepts used in the proof? This is a basic question in logic which, for proofs in weak theories or in propositional logic, is tied to fundamental difficult issues in computational complexity. In particular, showing that NP/=coNP is equivalent to showing that there is no propositional proof system which has short refutations of every contradiction. We will study variations of this question for a range of proof systems. These often have a combinatorial or algebraic nature, or can arise from certificates that a formula is unsatisfiable, produced by a practical SAT solver. We will make progress by understanding, in terms of first-order logic, the high-level kinds of reasoning captured by these systems, to gain insight into which kinds of statements are hard or easy for them and into the relationships between different systems. A foundation for this work is a good understanding of the strength of weak logical theories in proving basic mathematical statements.

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 <br>(dle <a href="http://www.vyzkum.cz/storage/att/E6EF7938F0E854BAE520AC119FB22E8D/Prevodnik_oboru_Frascati.pdf">převodníku</a>)

    BA - Obecná matematika

Termíny řešení

  • Zahájení řešení

    1. 1. 2023

  • Ukončení řešení

    31. 12. 2025

  • Poslední stav řešení

    B - Běžící víceletý projekt

  • Poslední uvolnění podpory

    27. 3. 2023

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

    CEP24-GA0-GA-R

  • Datum dodání záznamu

    19. 2. 2024

Finance

  • Celkové uznané náklady

    10 913 tis. Kč

  • Výše podpory ze státního rozpočtu

    10 664 tis. Kč

  • Ostatní veřejné zdroje financování

    249 tis. Kč

  • Neveřejné tuz. a zahr. zdroje finan.

    0 tis. Kč