期刊名称:Electronic Colloquium on Computational Complexity
印刷版ISSN:1433-8092
出版年度:1997
卷号:1997
出版社:Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要:Recently Ajtai showed that
to approximate the shortest lattice vector in the $l_2$-norm within a
factor $(1+2^{-\mbox{\tiny dim}^k})$, for a sufficiently large
constant $k$, is NP-hard under randomized reductions.
We improve this result to show that
to approximate a shortest lattice vector within a
factor $(1+ \mbox{dim}^{-\epsilon})$, for any
$\epsilon>0$, is NP-hard under randomized reductions.
Our proof also works for arbitrary $l_p$-norms, $1 \leq p < \infty$.
关键词:Approximation, lattices, NP-hardness, shortest vector problem