Enumerace v informatice a optimalizaci
Cíle projektu
Cílem projektu je pokrok v informatice a optimalizaci pomocí enumerací. Projekt má 3 části. Nejprve chceme studovat dolní odhady složitosti. Chceme se pokusit najít souvislost mezi determinatskou složitostí a aditivní determinatskou složitostí Isingovy partiční funkce, kde byl nedávno dokázán exponenciální dolní odhad. Za druhé chceme porozumēt složitosti problému grafového izomorfismu studiem hypotézy že neizomorfní chordální grafy jsou rozlišitelné partiční funkcí Pottsova modelu v mēnícím se magnetickém poli. Tato funkce je ekvivalentni dekoraci Tuttova polynomu a problém grafového izomorfismus je postačující charakterizovat pro chordální grafy. Nakonec chceme studovat klasické i kvantové počítání Isingova problému.
Klíčová slova
complexity lower boundsIsing partition functionalgebraic complexitydeterminantpermanentPfaffian methodquadratic formsgraph embeddinggraph isomorphismchromatic polynomialTutte polynomialmax-cut problemquantum computingexterior algebradual codes
Veřejná podpora
Poskytovatel
Grantová agentura České republiky
Program
Standardní projekty
Veřejná soutěž
Standardní projekty 17 (SGA0201300005)
Hlavní účastníci
Univerzita Karlova / Matematicko-fyzikální fakulta
Druh soutěže
VS - Veřejná soutěž
Číslo smlouvy
13-21988S
Alternativní jazyk
Název projektu anglicky
Enumeration in informatics and optimization
Anotace anglicky
The aim of this project is to make substantial advances in Theoretical Computer Science and Optimization by using recently developed enumerative methods. The project has three parts. First, we want to contribute to theory of computational intractability by studying complexity lower bounds. We want to relate additive determinantal complexity, where exponential lower bound (co-authored by me) was established recently in terms of Arf-invariant formula and proof of Norine' s conjecture for the Ising partition function, to determinantal complexity. Secondly, we want to advance understanding complexity of graph isomorphism by studying the conjecture that non-isomorphic chordal graphs are detected by the partition function of the Potts model in variable magnetic field; this function is equivalent to a decorated Tutte polynomial, and isomorphism problem of general graphs is equivalent to isomorphism problem for chordal graphs. Finally, we want to deepen connections between Computing and Physics. Specifically we study classic and quantum Ising problem computation.
Vědní obory
Kategorie VaV
ZV - Základní výzkum
CEP - hlavní obor
IN - Informatika
CEP - vedlejší obor
—
CEP - další vedlejší obor
—
OECD FORD - odpovídající obory
(dle převodníku)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
Projekt přinesl nové výsledky v některých oblastech návrhu. Řešitel předložil přínos publikovaných výsledků, výsledky byly zveřejněné ve třech hlavních publikacích. Řešitel se nevěnoval plnění všech původně navržených cílů projektu (např. kvantové počítání), aniž by vysvětlil důvod, kvalita publikací je spíše průměrná.
Termíny řešení
Zahájení řešení
1. 2. 2013
Ukončení řešení
25. 4. 2019
Poslední stav řešení
U - Ukončený projekt
Poslední uvolnění podpory
11. 4. 2017
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
CEP20-GA0-GA-U/01:1
Datum dodání záznamu
2. 7. 2020
Finance
Celkové uznané náklady
2 577 tis. Kč
Výše podpory ze státního rozpočtu
2 577 tis. Kč
Ostatní veřejné zdroje financování
0 tis. Kč
Neveřejné tuz. a zahr. zdroje finan.
0 tis. Kč
Základní informace
Uznané náklady
2 577 tis. Kč
Statní podpora
2 577 tis. Kč
100%
Poskytovatel
Grantová agentura České republiky
CEP
IN - Informatika
Doba řešení
01. 02. 2013 - 25. 04. 2019