The computation of the Betti numbers of an elliptic space is a NP-hard problem

被引：3

作者：

Garvín, A ^{[1
]}

Lechuga, L ^{[1
]}

机构：

[1] Univ Malaga, Escuela Univ Politecn, Dept Matemat Aplicada, E-29071 Malaga, Spain

来源：

TOPOLOGY AND ITS APPLICATIONS | 2003年 / 131卷 / 03期

关键词：

rational homotopy; complexity; NP-hard problem;

D O I：

10.1016/S0166-8641(02)00340-1

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

Let S a 1-connected space such that pi* (S) circle times Q and H*(S; Q) are both finite-dimensional. Then, using the Sullivan model as a codification for S, we prove that the computation of the Betti numbers of S is a NP-hard problem. (C) 2002 Elsevier Science B.V. All rights reserved.

引用

页码：235 / 238

页数：4

共 6 条

[1] DIOPHANTINE EQUATIONS, HILBERT SERIES, AND UNDECIDABLE SPACES [J].

ANICK, DJ .

ANNALS OF MATHEMATICS, 1985, 122 (01) :87-112

[2]

ANICK DJ, 1986, LECT NOTES APPL MATH, V114, P1

[3]

[Anonymous], 1979, Computers and Intractablity: A Guide to the Theoryof NP-Completeness

[4] FINITE COMPUTABILITY OF POSTNIKOV COMPLEXES [J].

BROWN, EH .

ANNALS OF MATHEMATICS, 1957, 65 (01) :1-20

[5]

Felix Y., 2000, GRADUATE TEXTS MATH, V205

[6] Complexity in rational homotopy [J].

Lechuga, L ;

Murillo, A .

TOPOLOGY, 2000, 39 (01) :89-94

← 1 →