Algebraický přístup k problému splnitelnosti omezujících podmínek
Veřejná podpora
Poskytovatel
Ministerstvo školství, mládeže a tělovýchovy
Program
KONTAKT
Veřejná soutěž
—
Hlavní účastníci
—
Druh soutěže
M2 - Mezinárodní spolupráce
Číslo smlouvy
1484/2009-32
Alternativní jazyk
Název projektu anglicky
An Algebraic Approach to the Constraint Satisfaction Problem
Anotace anglicky
The main goal of the cooperation is to provide an opportunity for Czech and Polish researchers to share their experience and exchange the ideas concerning the Constraint Satisfaction Problem, namely the dichotomy question. The cooperation has already been initiated with a number of visits of polish members in Czech Republic which resulted in a significant contribution to the development of the subject. The specific goals of the cooperation are designed in order to fully utilize the potential of an algebraic approach -- a potential already proved by the previous achievement of the authors of this application~(in a cooperation with Todd Niven). During the cooperation we want to enrich the collection of classes for which the dichotomy is known, concentrating on directed graphs, and thus developing the theory towards proving~(or disproving) the CSP dichotomy conjecture. The first step is to apply the algebraic tools for classes of digraphs with known dichotomies: oriented paths, oriented cycles, or
Vědní obory
Kategorie VaV
ZV - Základní výzkum
CEP - hlavní obor
BA - Obecná matematika
CEP - vedlejší obor
IN - Informatika
CEP - další vedlejší obor
—
OECD FORD - odpovídající obory <br>(dle <a href="http://www.vyzkum.cz/storage/att/E6EF7938F0E854BAE520AC119FB22E8D/Prevodnik_oboru_Frascati.pdf">převodníku</a>)
10101 - Pure mathematics<br>10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
Hodnocení dokončeného projektu
Hodnocení poskytovatelem
U - Uspěl podle zadání (s publikovanými či patentovanými výsledky atd.)
Zhodnocení výsledků projektu
Výsledkem projektu je vyřešení Larose-Zádoriho hypotézy o konečné šířce a nalezení dosud nejsilněšího kritéria pro NP-úplnost CSP. Výsledky byly přijaty do špičkových časopisů a prezentovány na elitních konferencích.
Termíny řešení
Zahájení řešení
1. 1. 2008
Ukončení řešení
31. 12. 2009
Poslední stav řešení
U - Ukončený projekt
Poslední uvolnění podpory
9. 3. 2009
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
CEP10-MSM-ME-U/01:1
Datum dodání záznamu
30. 6. 2010
Finance
Celkové uznané náklady
90 tis. Kč
Výše podpory ze státního rozpočtu
85 tis. Kč
Ostatní veřejné zdroje financování
5 tis. Kč
Neveřejné tuz. a zahr. zdroje finan.
0 tis. Kč