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

Перейти к навигации Перейти к поиску
Строка 21: Строка 21:


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




Строка 27: Строка 27:




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




Строка 33: Строка 33:




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




Источник — http://pco.iis.nsk.su/wega/index.php/Задача_о_кратчайшем_векторе