Charakterizace a efektivní řešitelnost constraintových jazyků pomocí logických metod

Poskytovatel

Grantová agentura České republiky

Program

Standardní projekty

Veřejná soutěž

SGA0202500001

Hlavní účastníci

Univerzita Karlova / Matematicko-fyzikální fakulta

Druh soutěže

VS - Veřejná soutěž

Číslo smlouvy

25-16324S

Název projektu anglicky

Characterization and tractability of constraint languages via logical methods

Anotace anglicky

Constraint satisfaction is a unifying framework and a powerful paradigm for expressing and solving combinatorial tasks from a wide range of real-life applications. Our understanding of the complexity landscape of constraint languages has recently undergone rapid development fuelled by improvements to the structural theory in connection with the resolution of the CSP dichotomy conjecture and the establishment of the algebraic framework for Promise CSP. The fundamental tools are standardized reductions based on primitive positive (pp-) definability and its generalizations, used as means to understand the structure of solution sets. The proposed project aims to enhance the state-of-art methods based on inspection of the structure of such pp-definability-based reductions and apply them to resolve important open problems in three areas: few subpowers and learnability and evaluability of solution sets, solvability in nondeterministic logspace via Linear Datalog, and progress towards full classification of constraint languages and Promise CSP templates modulo pp-constructibility.

Kategorie VaV

ZV - Základní výzkum

OECD FORD - hlavní obor

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

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>)

AF - Dokumentace, knihovnictví, práce s informacemi<br>BC - Teorie a systémy řízení<br>BD - Teorie informace<br>IN - Informatika

Zahájení řešení

1. 1. 2025

Ukončení řešení

31. 12. 2027

Poslední stav řešení

Z - Začínající víceletý projekt

Poslední uvolnění podpory

—

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

CEP25-GA0-GA-R

Datum dodání záznamu

27. 2. 2025

Celkové uznané náklady

6 185 tis. Kč

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

5 892 tis. Kč

Ostatní veřejné zdroje financování

293 tis. Kč

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

0 tis. Kč