Approximating CVP to within almost-polynomial factors is NP-hard (Q1878613): Difference between revisions

The lattice \(L(v_1,\dots,v_n)\) for linearly independent vectors \(v_1,\dots,v_n\in R^k\) for some \(k\) is the set \(\{a_1v_1+\dots+a_nv_n\mid a_1,\dots,v_n\in \mathbb Z\}\). The Closest Vector Problem (CVP) consists of, given a lattice \(L\) and a vector \(y\), finding a vector in \(L\) with minimal distance (in a certain norm) to \(y\). This problem has been studied for more than 100 years. It is known to be NP-hard for any \(l_p\) norm. Moreover, it is known that if CVP can be approximated to within any constant factor then \(\text{NP} = \text{P}\), and that if CVP can be approximated to within a factor \(2^{(\log n)^{1-\epsilon}}\) (for any \(\epsilon>0\)) then \(\text{NP}\subseteq\text{DTIME}(2^{(\log n)^{O(1)}})\). The present paper proves better non-approximability results: It is shown that if CVP can be approximated to within a factor of \(2^{\log n\over\log\log n}=n^{1\over\log\log n}\) (for any \(\epsilon>0\), so-called ``almost polynomial factors'') then \(\text{NP} =\text{P}\). The proof involves a problem, called Super Sat in the paper, which might be interesting in its own right. It can be seen as a gap version of the well-known constraint satisfiability problem for finite domains.