Název:
Výpočetní homotopická teorie
Překlad názvu:
Computational Homotopy Theory
Autoři:
Krčál, Marek ; Matoušek, Jiří (vedoucí práce) ; Pultr, Aleš (oponent) ; Romero Ibáñez, Ana (oponent) Typ dokumentu: Disertační práce
Rok:
2013
Jazyk:
eng
Abstrakt: [eng][cze] of doctoral thesis "Computational Homotopy Theory": We consider several basic problems of algebraic topology, with connections to combinatorial and geometric questions, from the point of view of compu- tational complexity. The extension problem asks, given topological spaces X, Y , a subspace A ⊆ X, and a (continuous) map f : A → Y , whether f can be extended to a map X → Y . For computational purposes, we assume that A, X, Y are represented as finite simplicial complexes and f as a simplicial map. We study the problem under the assumption that, for some d ≥ 1, Y is d- connected, otherwise the problem is undecidable by uncomputability of the fundamental group; We prove that, this problem is still undecidable for dim X = 2d + 2. On the other hand, for every fixed dim X ≤ 2d + 1, we obtain an algorithm that solves the extension problem in polynomial time. We obtain analogous complexity results for the problem of determining the set of homotopy classes of maps X → Y . We also consider the computation of the homotopy groups πk(Y ), k ≥ 2, for a 1-connected Y . Their computability was established by Brown in 1957; we show that πk(Y ) can be computed in polynomial time for every fixed k ≥ 2. On the other hand, we prove that computing πk(Y ) is #P-hard if k is a part of input. It is a strengthening of...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...
Klíčová slova:
computational complexity; homotopy theory; Postnikov systems; homotopická teorie; Postnikovovy systémy; výpočetní složitost