POLYNOMIAL-TIME COMPUTATION OF HOMOTOPY GROUPS AND POSTNIKOV SYSTEMS IN FIXED DIMENSION
The result's identifiers
Result code in 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>
Alternative codes found
RIV/00216224:14310/14:00073990
Result on the web
<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>
Alternative languages
Result language
angličtina
Original language name
POLYNOMIAL-TIME COMPUTATION OF HOMOTOPY GROUPS AND POSTNIKOV SYSTEMS IN FIXED DIMENSION
Original language description
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
Czech name
—
Czech description
—
Classification
Type
J<sub>x</sub> - Unclassified - Peer-reviewed scientific article (Jimp, Jsc and Jost)
CEP classification
BD - Information theory
OECD FORD branch
—
Result continuities
Project
Result was created during the realization of more than one project. More information in the Projects tab.
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)
Others
Publication year
2014
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Name of the periodical
SIAM Journal on Computing
ISSN
0097-5397
e-ISSN
—
Volume of the periodical
43
Issue of the periodical within the volume
5
Country of publishing house
US - UNITED STATES
Number of pages
53
Pages from-to
1728-1780
UT code for WoS article
000344753500009
EID of the result in the Scopus database
—