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

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

Что касается приближенных решений, то алгоритм редукции решетки LLL был улучшен как с точки зрения времени работы, так и с точки зрения гарантии аппроксимации (см. работу [ ] и ссылки в ней). В настоящее время лучший (рандомизированный) алгоритм аппроксимации с  полиномиальным временем выполнения достигает коэффициента аппроксимации у = 2O(nloglogn/l°gn).