COMPUTATIONAL COMPLEXITY OF TOPOLOGICAL INVARIANTS

被引：1
作者：
Amann, Manuel [1 ]
机构：
[1] Univ Toronto, Dept Math, Toronto, ON M5S 2E4, Canada
来源：
PROCEEDINGS OF THE EDINBURGH MATHEMATICAL SOCIETY | 2015年 / 58卷 / 01期
关键词：
computational complexity; cup length; Lusternik-Schnirelmann category; pure elliptic space;
D O I：
10.1017/S0013091514000455
中图分类号：
O1 [数学];
学科分类号：
0701 ; 070101 ;
摘要：
We answer the following question posed by Lechuga: given a simply connected space X with both H-*(X; Q) and pi(*)(X) circle times Q being finite dimensional, what is the computational complexity of an algorithm computing the cup length and the rational Lusternik-Schnirelmann category of X? Basically, by a reduction from the decision problem of whether a given graph is k-colourable for k >= 3, we show that even stricter versions of the problems above are NP-hard.
引用
收藏
页码：27 / 32
页数：6
相关论文
共 8 条
[1]  
Anick DavidJ., 1989, Computers in geometry and topology (Chicago, IL, 1986), V114, P1
[2]  
Felix Y., 2001, GRAD TEXT M, V205, DOI 10.1007/978-1-4613-0105-9
[3]  
Garey MR., 1979, Computers and Intractability
[4]  
A Guide to the Theory of NP-Completeness
[5]   The computation of the Betti numbers of an elliptic space is a NP-hard problem [J].
Garvín, A ;
Lechuga, L .
TOPOLOGY AND ITS APPLICATIONS, 2003, 131 (03) :235-238
[6]   A Groebner basis algorithm for computing the rational L.-S. category of elliptic pure spaces [J].
Lechuga, L .
BULLETIN OF THE BELGIAN MATHEMATICAL SOCIETY-SIMON STEVIN, 2002, 9 (04) :533-544
[7]   Complexity in rational homotopy [J].
Lechuga, L ;
Murillo, A .
TOPOLOGY, 2000, 39 (01) :89-94
[8]  
Sipser M., 2006, INTRO THEORY COMPUTA
1