Tensor Rank is Hard to Approximate

摘要

We prove that approximating the rank of a 3-tensor to within a factor of 1 + 1 1852 ? , for any 0" 0 , is NP-hard over any field. We do this via reduction from bounded occurrence 2-SAT.