[google:SVP NPに属する]

某大学から.
|・σ・)ノ [lab:keyword:現代格子史], D. Aharonov and O. Regev. "Lattice Problems in NP intersect coNP" (Journal of the ACM 52(5), pp. 749-765, 2005. Preliminary version in Proc. of FOCS 2004).
ガウス分布フーリエ解析を駆使することで, ユークリッド・ノルム下の近似度√nのSVPがNPに属することを証明している論文. MicciancioやKhotが示しているのはNP-hardの話なんでNPに属することは示してません.

以上, 親切の押し売りでした.

訂正: 酷いこと書いてるなぁ自分.
Decisional SVPがNPに属するのは当たり前. GapSVPでも当たり前. 最短ベクトルを証拠として持ってこればいいんだし. で, コメント欄の話になると.
Aharonov and Regevは近似度√nのcoGapCVPがNPに属していることを示している点が重要.