Notele lui Micciancio sunt corecte și modul standard de a explica lucrurile, așa că haideți să elaborăm câteva.
În primul rând, merită menționat că acest lucru nu are nimic de-a face cu (Gap)SVP în mod specific și totul de-a face cu ceea ce se numește promit probleme mai general.
O problemă de promisiune este o anumită relaxare a unei probleme de decizie standard. Ele sunt menite să relaxeze noțiunea de corectitudine pentru problema. Noțiunea standard de corectitudine poate fi rezumată „Algoritmul este corect pe toate intrările”. Există două relaxări naturale ale acestui lucru
Clase randomizate (cum ar fi BPP, ZPP, (co)RP).În orice caz anume, algoritmul trebuie să fie corect „în medie”, în cazul în care faceți o medie asupra alegerilor interne de monede aleatorii.
Promite probleme, în care ești bine cu algoritmul care face greșeli în „instanțe dificile”, dar trebuie să fie întotdeauna corect în „instanțe ușoare”.
În special, în cazurile dificile, un algoritm poate fi complet incorectă, și nu ne pasă. Atâta timp cât este corect în cazuri ușoare, spunem că este corect în general.
Pentru a aduce lucrurile înapoi la GapSVP, cazurile dificile sunt când $d\leq \lambda\leq \gamma d$. Deci spunem că un algoritm rezolvă GapSVP dacă
Dată un exemplu $(L, d)$ (o zăbrele și distanță legată) adică uşor, sens $\lambda_1(L)\leq d$ sau $\lambda_1(L)\geq \gamma d$, algoritmul returnează răspunsul corect
Având în vedere un exemplu greu, algoritmul returnează orice dorește. Nu ne pasă.
În special, având în vedere la fel hard instance de două ori, un algoritm ar putea returna ambele răspunsuri (nu trebuie să fie consecvent intern). Nu ne pasă --- ne pasă doar cum se descurcă algoritmul în cazurile „ușoare”, măsurate prin $\gamma$.
