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

Известно, что и <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].