Modul standard în care este oficializat SVP este astfel încât ceea ce cereți să nu fie cu adevărat relevant pentru a afișa $SVP\in\mathsf{NP}$.
Formalizarea tipică a SVP este (pentru o normă arbitrară $\lVert\cdot\rVert$ pe $\mathbb{R}^n$ --- rețineți că duritatea SVP poate depinde de alegerea particulară a normei):
Lăsa $n\în\mathbb{N}$, și $\gamma\in\mathbb{R}_{\geq 0}$. O instanță de SVP este o pereche $(\Lambda, \gamma)$, Unde $\Lambda\subseteq\mathbb{R}^n$ este o zăbrele și $\gamma$ o constantă. Spunem că o instanță SVP $(\Lambda,\gamma)$ acceptă dacă:
$$\min_{v\in\Lambda\setminus\{0\}}\lVert v\rVert \leq\gamma$$
și respingând altfel.
În ceea ce privește această formulare a problemei, NP este martor la o instanță de problemă $(\Lambda, \gamma)$ este orice vector $v\in\Lambda\setminus\{0\}$ astfel încât $\lVert v\rVert \leq \gamma$.
Acestea pot fi descrise în mod clar și ar trebui să fie clar și cum se poate verifica eficient dacă $(\Lambda,\gamma)$ acceptă sau respinge, dat un astfel de martor.
Desigur, întrebarea dvs. are o interpretare mai largă --- putem determina eficient dacă vreun vector candidat cel mai scurt $v$ este „de fapt” cel mai scurt vector din zăbrele? Nu sunt expert, dar:
- Nu cred că acest lucru este cunoscut în cel mai rău caz (dar nu sunt sigur)
- În cazul mediu (care este cel la care țin toată lumea), rezultă o concentrare suficient de puternică $\lambda_1(\Lambda)$ se stie ca nu conteaza.
În special, pentru majoritatea candidaților distribuiri „hard” peste grilaje $\Lambda\obține \mathcal{D}$, $\lambda_1(\Lambda)$ este foarte concentrat în jurul unei valori cunoscute, deci pentru a „verifica” dacă vreun vector candidat $v$ este cel mai scurt dintr-o rețea aleatorie $\Lambda$, este suficient să verificați dacă $\lVert v\rVert$ este aproape de valoarea cunoscută a $\mathbb{E}_{\Lambda\gets\mathcal{D}}[\lambda_1(\Lambda)]$.
Vezi de exemplu Grile aleatorii: teorie și practică, care include câteva indicații către lucrări matematice relevante.
