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

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

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

Дополнительную информацию см. в оригинальных статьях [2, 11] и [12, гл. 2]. Вводные презентации алгоритма LLL также можно найти во многих других текстах, например, [5, глава 16] и [15, глава 27]. Интересно отметить, что CVP по крайней мере так же сложен, как SVP (см. [12 , глава 2]), в том смысле, что любой алгоритм, решающий задачу <math>CVP_\gamma</math>, может быть эффективно адаптирован для решения задачи <math>SVP_\gamma</math> с тем же коэффициентом аппроксимации.

Известно, что и <math>SVP_\gamma</math>, и <math>CVP_\gamma</math> являются NP-трудными при точных (y = 1) или даже приближенных версиях для малых значений y – например, при постоянной у, не зависящей от размерности. (Самые актуальные результаты см. в [13, гл. 3 и 4] и [4,10]). Поэтому, скорее всего, не существует эффективного алгоритма для точного решения этих задач в произвольной размерности. Для любой фиксированной размерности n обе задачи, и SVP, и CVP, могут быть точно решены за полиномиальное время с помощью алгоритма Каннана [9]. Однако время работы зависит от размерности решетки по формуле <math>n^{O(n)}</math>. Используя рандомизацию, можно вероятностно решить точную задачу SVP с затратами <math>2^{O(n)}</math> времени и памяти при помощи алгоритма на основе решета, предложенного Айтаем, Кумаром и Сивакумаром [1].