GapSVP ∈ NP

Inclusion · folklore

Statement

For every $\gamma \ge 1$, the promise problem ${\mathrm{GapSVP}}_{\gamma }$ (GapSVP) is in NP: on a yes-instance, a nonzero lattice vector of norm at most $d$ is a witness that the verifier checks by solving a linear system over the integers — folklore.

Notes

• The complement is in $\mathbf{NP}$ for $\gamma \ge c\sqrt{n}$ with a suitable constant $c$ (GapSVP ∈ coNP) — AR04 — and in $\mathbf{AM}$ for $\gamma \ge c\sqrt{n/\log n}$ for a constant $c>0$ (GapSVP ∈ coAM) — GG00.