Denna tjänst avvecklas 2026-01-19. Läs mer här (länk)

NEAREST LATTICE VECTOR

• INSTANCE: Lattice basis $\{b_1,\ldots,b_m\}$ where $b_i\in Z^k$, a point $b_0\in Q^k$, and a positive integer p.

• SOLUTION: A vector b in the lattice, where $b\ne b_0$.

• MEASURE: The distance between $b_0$ and b in the $\ell_p$ norm.

  
  

• Bad News: Not in APX [35].

• Comment: Not approximable within $2^{\log^{1-\varepsilon } mp}$ for any $\varepsilon >0$ unless NP$\subset$QP. The special case where $b_0$ is the zero vector and $p=\infty$ is not approximable within $2^{\log^{0.5-\varepsilon } mp}$ for any $\varepsilon >0$ unless NP$\subset$QP [35].