Задача о кратчайшем векторе: различия между версиями

Проблема поиска эффективного (за полиномиальное время) решения <math>SVP_\gamma</math> для решеток произвольной размерности была впервые решена при помощи знаменитого алгоритма редукции решеток Ленстры, Ленстры и Ловаса [ ], получившего известность как алгоритм LLL.

Теорема 1. Существует алгоритм решения задачи <math>SVP_\gamma</math> за полиномиальное время для у = (2/p3)n, где n – ранг входной решетки.

Алгоритм LLL не ограничивается простым нахождением относительно короткого вектора решетки: он вычисляет так называемый редуцированный базис для входной решетки, т. е. полный базис, состоящий из относительно более коротких векторов решетки. Вскоре после разработки алгоритма LLL Бабай [2] показал, что редуцированные базисы могут быть использованы для эффективного решения CVPу также в пределах аналогичных коэффициентов аппроксимации.

Следствие 1. Существует алгоритм решения задачи <math>CVP_\gamma</math> за полиномиальное время для у = O(2/p3)n, где n – ранг входной решетки.