|
|
Computational Homotopy Theory
Krčál, Marek ; Matoušek, Jiří (vedoucí práce) ; Pultr, Aleš (oponent) ; Romero Ibáñez, Ana (oponent)
dizertační práce "Výpočetní homotopická teorie": Tato práce studuje výpočetní složitost několika základních problémů algebraické topologie, které mají souvislost s otázkami v kombinatorice a výpočetní ge- ometrií. Problém rozšiřitelnosti je zadán topologickými prostory X, Y, podpros- torem A ⊆ X a (spojitým) zobrazením f : A → Y . A otázka je, zda f může být rozšířeno na celý prostor X. Předpokládáme, že X, Y a A jsou zadány jako konečné simpliciální komplexy a f jako simpliciální zobrazení. Výpočetní složitost budeme zkoumat za předpokladu, že Y je d-souvislý pro nějaké d ≥ 1. Jinak je známo, že z teorie grup plyne, že problém rozšiřitel- nosti je nerozhodnutelný. Zde dokážeme, že rozšiřitelnost je i při tomto předpokladu nerozhod- nutelná, pokud dim X dosáhne hodnoty 2d+2. Na druhou stranu pro každou pevnou hodnotu dim X ≤ 2d + 1 nalezneme algoritmus, který řeší problém rozšiřitelnosti v polynomiálním čase. Ukážeme, že složitost výpočtu množiny všech homotopických tříd zo- brazení X → Y má podobnou charakteristiku. Dále uvážíme problém homotopických grup πk(Y ) pro 1-souvislý prostor Y a dimenzi k ≥ 2. První algoritmus na jejich výpočet našel Brown v roce 1957. My ukážeme, že πk(Y ) lze vypočíst v polynomiálním čase pro každou pevnou dimenzi k ≥ 2. Na druhou stranu dokážeme, že výpočet πk(Y ) je...
|
|
|
Computational Homotopy Theory
Krčál, Marek ; Matoušek, Jiří (vedoucí práce) ; Pultr, Aleš (oponent) ; Romero Ibáñez, Ana (oponent)
dizertační práce "Výpočetní homotopická teorie": Tato práce studuje výpočetní složitost několika základních problémů algebraické topologie, které mají souvislost s otázkami v kombinatorice a výpočetní ge- ometrií. Problém rozšiřitelnosti je zadán topologickými prostory X, Y, podpros- torem A ⊆ X a (spojitým) zobrazením f : A → Y . A otázka je, zda f může být rozšířeno na celý prostor X. Předpokládáme, že X, Y a A jsou zadány jako konečné simpliciální komplexy a f jako simpliciální zobrazení. Výpočetní složitost budeme zkoumat za předpokladu, že Y je d-souvislý pro nějaké d ≥ 1. Jinak je známo, že z teorie grup plyne, že problém rozšiřitel- nosti je nerozhodnutelný. Zde dokážeme, že rozšiřitelnost je i při tomto předpokladu nerozhod- nutelná, pokud dim X dosáhne hodnoty 2d+2. Na druhou stranu pro každou pevnou hodnotu dim X ≤ 2d + 1 nalezneme algoritmus, který řeší problém rozšiřitelnosti v polynomiálním čase. Ukážeme, že složitost výpočtu množiny všech homotopických tříd zo- brazení X → Y má podobnou charakteristiku. Dále uvážíme problém homotopických grup πk(Y ) pro 1-souvislý prostor Y a dimenzi k ≥ 2. První algoritmus na jejich výpočet našel Brown v roce 1957. My ukážeme, že πk(Y ) lze vypočíst v polynomiálním čase pro každou pevnou dimenzi k ≥ 2. Na druhou stranu dokážeme, že výpočet πk(Y ) je...
|
host ::
RSS.