Стандартный способ формализации SVP заключается в том, что то, что вы спрашиваете, на самом деле не имеет отношения к показу. $СВП\в\mathsf{НП}$.
Типичная формализация SVP (для произвольной нормы $\lVert\cdot\rVert$ на $\mathbb{R}^n$ --- учтите, что твердость СВП может зависеть от конкретного выбора нормы):
Позволять $n\in\mathbb{N}$, и $\gamma\in\mathbb{R}_{\geq 0}$. Экземпляр SVP представляет собой пару $(\лямбда,\гамма)$, куда $\Lambda\subseteq\mathbb{R}^n$ представляет собой решетку, и $\гамма$ константа. Мы говорим, что экземпляр SVP $(\лямбда,\гамма)$ принимает, если:
$$\min_{v\in\Lambda\setminus\{0\}}\lVert v\rVert \leq\gamma$$
и отвергая в противном случае.
С точки зрения этой постановки проблемы, NP свидетельствует о экземпляре проблемы. $(\лямбда,\гамма)$ любой вектор $v\in\Lambda\setminus\{0\}$ такой, что $\lVert v\rVert \leq \gamma$.
Ясно, что их можно эффективно описать, и также должно быть ясно, как можно эффективно проверить, действительно ли $(\лямбда,\гамма)$ принимает или отвергает, учитывая такой свидетель.
Конечно, ваш вопрос имеет более широкую интерпретацию --- можем ли мы эффективно определить, является ли какой-либо кандидат кратчайшим вектором $v$ является «на самом деле» кратчайшим вектором в решетке? Я не эксперт, но:
- Я не верю, что это известно в худшем случае (но не уверен)
- В среднем случае (который всех волнует) достаточно сильная концентрация приводит к $\лямбда_1(\лямбда)$ известно, что это не имеет значения.
В частности, для большинства возможных «жестких» распределений по решеткам $\Lambda\gets\mathcal{D}$, $\лямбда_1(\лямбда)$ сильно сконцентрирован вокруг некоторого известного значения, поэтому для «проверки», если какой-либо вектор-кандидат $v$ является кратчайшим в некоторой случайной решетке $\лямбда$, достаточно проверить, $\lVert v\rVert$ близко к известному значению $\mathbb{E}_{\Lambda\gets\mathcal{D}}[\lambda_1(\Lambda)]$.
См. например Случайные решетки: теория и практика, который включает в себя некоторые указатели на соответствующие математические работы.
