Заметки Миччанчио верны и являются стандартным способом объяснения вещей, так что давайте уточним некоторые из них.
Во-первых, стоит упомянуть, что это не имеет ничего общего с (Gap)SVP конкретно, а все, что связано с тем, что называется обещать проблемы в более общем смысле.
Проблема обещаний — это некоторое ослабление стандартной проблемы принятия решений. Они призваны ослабить представление о правильность для проблемы. Стандартное понятие корректности можно резюмировать: «Алгоритм корректен на всех входных данных». Есть два естественных расслабления этого
Рандомизированные классы (например, BPP, ZPP, (co)RP).В любом конкретном случае алгоритм теперь должен быть правильным только «в среднем», когда вы усредняете внутренний выбор случайных монет.
Обещайте проблемы, когда вы согласны с тем, что алгоритм делает ошибки в «сложных случаях», но он всегда должен быть правильным в «легких случаях».
В частности, на сложных экземплярах алгоритм может быть совершенно неправильно, а нам все равно. Пока это правильно в простых случаях, мы говорим, что это правильно в целом.
Чтобы вернуться к GapSVP, трудные случаи — это когда $d\leq\лямбда\leq\gamma d$. Поэтому мы говорим, что алгоритм решает GapSVP, если
Учитывая экземпляр $(L, д)$ (решетка и граница расстояния), то есть легкий, смысл $\lambda_1(L)\leqd$ или же $\lambda_1(L)\geq\gamma d$, алгоритм возвращает правильный ответ
Учитывая жесткий экземпляр, алгоритм возвращает все, что хочет. Нам все равно.
В частности, с учетом тем же hard дважды, алгоритм может вернуть оба ответа (он не обязательно должен быть внутренне непротиворечивым). Нас не волнует --- нас интересует только то, как работает алгоритм на "простых" экземплярах, измеряемых $\гамма$.
