Idioma:

Most Tensor Problems Are NP-Hard

Hillar, Christopher J ; Lim, Lek-Heng

Journal of the ACM, 2013-11, Vol.60 (6), p.1-39 [Periódico revisado por pares]

New York, NY: ACM

Texto completo disponível

Citações Citado por

Enviar para

Título:
Most Tensor Problems Are NP-Hard
Autor: Hillar, Christopher J ; Lim, Lek-Heng
Assuntos: Algorithmics. Computability. Computer arithmetics ; Algorithms ; Applied sciences ; Approximation ; bivariate matrix polynomials ; Computer science; control theory; systems ; Eigen values ; Exact sciences and technology ; hyperdeterminants ; Linear algebra ; Linear equations ; Mathematical problems ; nonnegative definite tensors ; NP-hardness ; Numerical analysis ; Numerical multilinear algebra ; P-hardness ; polynomial time approximation schemes ; Studies ; symmetric tensors ; system of multilinear equations ; tensor eigenvalue ; tensor rank ; tensor singular value ; tensor spectral norm ; Theoretical computing ; undecidability ; VNP-hardness
É parte de: Journal of the ACM, 2013-11, Vol.60 (6), p.1-39
Notas: ObjectType-Article-2
SourceType-Scholarly Journals-1
ObjectType-Feature-1
content type line 23
Descrição: We prove that multilinear (tensor) analogues of many efficiently computable problems in numerical linear algebra are NP-hard. Our list includes: determining the feasibility of a system of bilinear equations, deciding whether a 3-tensor possesses a given eigenvalue, singular value, or spectral norm; approximating an eigenvalue, eigenvector, singular vector, or the spectral norm; and determining the rank or best rank-1 approximation of a 3-tensor. Furthermore, we show that restricting these problems to symmetric tensors does not alleviate their NP-hardness. We also explain how deciding nonnegative definiteness of a symmetric 4-tensor is NP-hard and how computing the combinatorial hyperdeterminant is NP-, #P-, and VNP-hard.
Editor: New York, NY: ACM
Idioma: Inglês

Links

View record in Pascal Francis

Voltar para lista de resultados

Realização: Logos de Redes Sociais:

Most Tensor Problems Are NP-Hard

Hillar, Christopher J ; Lim, Lek-Heng

New York, NY: ACM

Buscando em bases de dados remotas. Favor aguardar.