Cách tiêu chuẩn mà SVP được chính thức hóa sao cho những gì bạn hỏi không thực sự liên quan đến việc hiển thị $SVP\in\mathsf{NP}$.
Hình thức hóa điển hình của SVP là (đối với một định mức tùy ý $\lVert\cdot\rVert$ trên $\mathbb{R}^n$ --- lưu ý rằng độ cứng của SVP có thể phụ thuộc vào sự lựa chọn định mức cụ thể):
Để cho $n\in\mathbb{N}$, và $\gamma\in\mathbb{R}_{\geq 0}$. Một thể hiện của SVP là một cặp $(\Lambda, \gamma)$, ở đâu $\Lambda\subseteq\mathbb{R}^n$ là mạng tinh thể và $\gamma$ một hằng số. Chúng tôi nói rằng một phiên bản SVP $(\Lambda,\gamma)$ được chấp nhận nếu:
$$\min_{v\in\Lambda\setminus\{0\}}\lVert v\rVert \leq\gamma$$
và từ chối khác.
Về mặt hình thành vấn đề này, NP chứng kiến một trường hợp vấn đề $(\Lambda, \gamma)$ là một vectơ bất kỳ $v\in\Lambda\setminus\{0\}$ như vậy mà $\lVert v\rVert \leq \gamma$.
Những điều này rõ ràng có thể được mô tả một cách hiệu quả và cũng phải rõ ràng về cách người ta có thể xác minh một cách hiệu quả liệu $(\Lambda,\gamma)$ là chấp nhận hay từ chối, đưa ra một nhân chứng như vậy.
Tất nhiên, câu hỏi của bạn có cách diễn giải rộng hơn --- liệu chúng ta có thể xác định một cách hiệu quả liệu một số vectơ ngắn nhất ứng cử viên $v$ là "thực sự" là vectơ ngắn nhất trong mạng? Tôi không phải là một chuyên gia, nhưng:
- Tôi không tin điều này được biết đến trong trường hợp xấu nhất (nhưng tôi không chắc)
- Trong trường hợp trung bình (là điều mà mọi người đều quan tâm), sự tập trung đủ mạnh dẫn đến $\lambda_1(\Lambda)$ được biết rằng nó không quan trọng.
Đặc biệt, đối với hầu hết các bản phân phối "cứng" trên mạng $\Lambda\được \mathcal{D}$, $\lambda_1(\Lambda)$ được tập trung cao độ xung quanh một số giá trị đã biết, vì vậy để "kiểm tra" xem một số vectơ ứng cử viên $v$ là ngắn nhất trong một số mạng ngẫu nhiên $\Lambda$, nó đủ để kiểm tra nếu $\lVert v\rVert$ gần với giá trị đã biết của $\mathbb{E}_{\Lambda\gets\mathcal{D}}[\lambda_1(\Lambda)]$.
Xem ví dụ Mạng ngẫu nhiên: Lý thuyết và thực hành, bao gồm một số gợi ý cho công việc toán học có liên quan.
