The Super-SAT or SSAT problem was introduced by Dinur et al.(2002,2003) to prove the NP-hardness of approximation of two popular lattice problems - Shortest Vector Problem(SVP) and Closest Vector Problem(CVP). They conjectured that SSAT is NP-hard to approximate to within a factor of $n^c$ ($c>0$ is constant), where $n$ is the size of the SSAT instance. In this paper we prove this conjecture assuming the Projection Games Conjecture(PGC), given by Moshkovitz (2012). This implies hardness of approximation of SVP and CVP within polynomial factors, assuming PGC. We also reduce SSAT to the Nearest Codeword Problem(NCP) and Learning Halfspace Problem(LHP), as considered by Arora et al.(1997). This proves that both these problems are NP-hard to approximate within a factor of $N^{c'/\log\log n}$($c'>0$ is constant) where $N$ is the size of the instances of the respective problems. Assuming PGC these problems are proved to be NP-hard to approximate within polynomial factors.
翻译:Dinur等人(2002,2003年)提出了超级SAT或SSAT问题,以证明两个流行的悬浮问题 -- -- 最短矢量问题(SVP)和最接近矢量问题(CVP) -- -- 的近似近效硬度。他们推测SSAT很难接近近似于美元(c>0美元不变)的因数,而美元是SSAT实例的大小。在本文中,我们证明假定Moshkovitz(2012年)提供的投影游戏截图(PGC),这种假设是NP-硬度。这意味着SVP和CVP在多数值因素中的近近似性,假定PGC。我们还假设Aora等人(1997年)认为SSAT是近近于代码问题(NCP)和学习半空间问题(LHPH),将SSAT降低至近近于美元(NCP)和学习半空间问题(LHPH)的因数。这证明,这两个问题都是NP-硬度(c'0'0美元是长期的因数,因为美元与PGC问题相近似为问题。