POLYNOMIAL-TIME COMPUTATION OF HOMOTOPY GROUPS AND POSTNIKOV SYSTEMS IN FIXED DIMENSION

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F14%3A10286482" target="_blank" >RIV/00216208:11320/14:10286482 - isvavai.cz</a>

Nalezeny alternativní kódy

RIV/00216224:14310/14:00073990

Výsledek na webu

<a href="http://dx.doi.org/10.1137/120899029" target="_blank" >http://dx.doi.org/10.1137/120899029</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1137/120899029" target="_blank" >10.1137/120899029</a>

Jazyk výsledku

angličtina

Název v původním jazyce

POLYNOMIAL-TIME COMPUTATION OF HOMOTOPY GROUPS AND POSTNIKOV SYSTEMS IN FIXED DIMENSION

Popis výsledku v původním jazyce

For several computational problems in homotopy theory, we obtain algorithms with running time polynomial in the input size. In particular, for every fixed k }= 2, there is a polynomial-time algorithm that, for a 1-connected topological space X given as afinite simplicial complex, or more generally, as a simplicial set with polynomial-time homology, computes the kth homotopy group pi(k)(X), as well as the first k stages of a Postnikov system of X. Combined with results of an earlier paper, this yields apolynomial-time computation of [X, Y], i.e., all homotopy classes of continuous mappings X -> Y, under the assumption that Y is (k - 1)-connected and dim X {= 2k - 2. We also obtain a polynomial-time solution of the extension problem, where the input consists of finite simplicial complexes X -> Y, where Y is (k - 1)-connected and dim X {= 2k - 1, plus a subspace A subset of X and a (simplicial) map f : A -> Y, and the question is the extendability of f to all of X. The algorithms are ba

Název v anglickém jazyce

POLYNOMIAL-TIME COMPUTATION OF HOMOTOPY GROUPS AND POSTNIKOV SYSTEMS IN FIXED DIMENSION

Popis výsledku anglicky

For several computational problems in homotopy theory, we obtain algorithms with running time polynomial in the input size. In particular, for every fixed k }= 2, there is a polynomial-time algorithm that, for a 1-connected topological space X given as afinite simplicial complex, or more generally, as a simplicial set with polynomial-time homology, computes the kth homotopy group pi(k)(X), as well as the first k stages of a Postnikov system of X. Combined with results of an earlier paper, this yields apolynomial-time computation of [X, Y], i.e., all homotopy classes of continuous mappings X -> Y, under the assumption that Y is (k - 1)-connected and dim X {= 2k - 2. We also obtain a polynomial-time solution of the extension problem, where the input consists of finite simplicial complexes X -> Y, where Y is (k - 1)-connected and dim X {= 2k - 1, plus a subspace A subset of X and a (simplicial) map f : A -> Y, and the question is the extendability of f to all of X. The algorithms are ba

Druh

J_x - Nezařazeno - Článek v odborném periodiku (Jimp, Jsc a Jost)

CEP obor

BD - Teorie informace

OECD FORD obor

—

Projekt

Výsledek vznikl pri realizaci vícero projektů. Více informací v záložce Projekty.

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Rok uplatnění

2014

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název periodika

SIAM Journal on Computing

ISSN

0097-5397

e-ISSN

—

Svazek periodika

43

Číslo periodika v rámci svazku

5

Stát vydavatele periodika

US - Spojené státy americké

Počet stran výsledku

53

Strana od-do

1728-1780

Kód UT WoS článku

000344753500009

EID výsledku v databázi Scopus

—