Các ghi chú của Micciancio là chính xác và là cách tiêu chuẩn để giải thích mọi thứ, vì vậy hãy giải thích thêm một số.
Đầu tiên, điều đáng nói là điều này không liên quan gì đến (Gap) SVP cụ thể và mọi thứ liên quan đến cái được gọi là vấn đề về lời hứa tổng quát hơn.
Một vấn đề lời hứa là một sự nới lỏng nhất định của một vấn đề quyết định tiêu chuẩn. Chúng có nghĩa là để thư giãn các khái niệm về sự đúng đắn cho vấn đề. Khái niệm chuẩn về tính chính xác có thể được tóm tắt "Thuật toán đúng trên tất cả các đầu vào". Có hai thư giãn tự nhiên của điều này
Các lớp ngẫu nhiên (như BPP, ZPP, (co)RP).Trong bất kỳ trường hợp cụ thể nào, thuật toán hiện chỉ cần đúng " tính trung bình ", trong đó bạn tính trung bình cho các lựa chọn nội bộ của các đồng xu ngẫu nhiên.
Các vấn đề về hứa hẹn, trong đó bạn ổn với thuật toán mắc lỗi trong "trường hợp khó", nhưng nó luôn phải đúng với "trường hợp dễ".
Đặc biệt, trong các trường hợp khó khăn, một thuật toán có thể được hoàn toàn không chính xác, và chúng tôi không quan tâm. Miễn là nó đúng trong những trường hợp đơn giản, chúng tôi nói nó đúng về tổng thể.
Để đưa mọi thứ trở lại GapSVP, các trường hợp khó khăn là khi $d\leq \lambda\leq \gamma d$. Vì vậy, chúng tôi nói rằng một thuật toán giải quyết GapSVP nếu
Đưa ra một ví dụ $(L, d)$ (một mạng và giới hạn khoảng cách) đó là dễ dàng, Ý nghĩa $\lambda_1(L)\leq d$ hoặc $\lambda_1(L)\geq \gamma d$, thuật toán trả về câu trả lời đúng
Đưa ra một ví dụ khó, thuật toán trả về bất cứ thứ gì nó muốn. Chúng tôi không quan tâm.
Đặc biệt, đưa ra các như nhau hard hai lần, một thuật toán có thể trả về cả hai câu trả lời (nó không nhất thiết phải nhất quán bên trong). Chúng tôi không quan tâm --- chúng tôi chỉ quan tâm thuật toán hoạt động như thế nào trong các trường hợp "dễ dàng", được đo bằng $\gamma$.
