TENSOR RANK IS NP-COMPLETE

被引：390
作者：
HASTAD, J [1 ]
机构：
[1] ROYAL INST TECHNOL, STOCKHOLM 70, SWEDEN
来源：
JOURNAL OF ALGORITHMS-COGNITION INFORMATICS AND LOGIC | 1990年 / 11卷 / 04期
关键词：
D O I：
10.1016/0196-6774(90)90014-6
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
We prove that computing the rank of a three-dimensional tensor over any finite field is NP-complete. Over the rational numbers the problem is NP-hard. © 1990.
引用
收藏
页码：644 / 654
页数：11
相关论文
共 10 条
[1]   ON THE ALGORITHMIC COMPLEXITY OF ASSOCIATIVE ALGEBRAS [J].
ALDER, A ;
STRASSEN, V .
THEORETICAL COMPUTER SCIENCE, 1981, 15 (02) :201-211
[2]  
Bshouty N. H., 1988, 29th Annual Symposium on Foundations of Computer Science (IEEE Cat. No.88CH2652-6), P64, DOI 10.1109/SFCS.1988.21922
[3]  
COOK SA, 3RD P ANN ACM S THEO, P151
[4]  
COPPERSMITH D, 19TH P ANN ACM S THE, P1
[5]  
Garey M.R., 1979, COMPUTERS INTRACTABI, V174
[6]   ON THE COMPLEXITY OF COMPUTING BILINEAR-FORMS WITH [0,1] CONSTANTS [J].
GONZALEZ, T ;
JAJA, J .
JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 1980, 20 (01) :77-95
[7]  
HASTAD J, 1989, LECT NOTES COMPUT SC, V372, P451
[8]   MINIMIZING NUMBER OF MULTIPLICATIONS NECESSARY FOR MATRIX MULTIPLICATION [J].
HOPCROFT, JE ;
KERR, LR .
SIAM JOURNAL ON APPLIED MATHEMATICS, 1971, 20 (01) :30-&
[9]   RANK AND OPTIMAL COMPUTATION OF GENERIC TENSORS [J].
STRASSEN, V .
LINEAR ALGEBRA AND ITS APPLICATIONS, 1983, 52-3 (JUL) :645-685
[10]  
STRASSEN V, 1988, J REINE ANGEW MATH, V384, P102
1