NP-Hardness of Tensor Network Contraction Ordering

Autor:	Xu, Jianyu, Zhang, Hanwen, Liang, Ling, Deng, Lei, Xie, Yuan, Li, Guoqi
Rok vydání:	2023
Předmět:	Computer Science - Computational Complexity Mathematics - Combinatorics 05C35 05C76 F.2.2
Druh dokumentu:	Working Paper
Popis:	We study the optimal order (or sequence) of contracting a tensor network with a minimal computational cost. We conclude 2 different versions of this optimal sequence: that minimize the operation number (OMS) and that minimize the time complexity (CMS). Existing results only shows that OMS is NP-hard, but no conclusion on CMS problem. In this work, we firstly reduce CMS to CMS-0, which is a sub-problem of CMS with no free indices. Then we prove that CMS is easier than OMS, both in general and in tree cases. Last but not least, we prove that CMS is still NP-hard. Based on our results, we have built up relationships of hardness of different tensor network contraction problems. Comment: Jianyu Xu and Hanwen Zhang are equal contributors. 10 pages (reference and appendix excluded), 20 pages in total, 6 figures
Databáze:	arXiv
Externí odkaz:	http://arxiv.org/abs/2310.06140 Zobrazit plný text záznamu View this record from Arxiv