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

Что касается приближенных решений, то алгоритм редукции решетки LLL был улучшен как с точки зрения времени работы, так и с точки зрения гарантии аппроксимации (см. работу [14] и ссылки в ней). В настоящее время лучший (рандомизированный) алгоритм аппроксимации с полиномиальным временем выполнения достигает коэффициента аппроксимации <math>\gamma = 2^{O(n \; log \; log \; n / log \; n)}</math>.

Основной открытой задачей в вычислительном исследовании решеток является определение сложности приближенных алгоритмов <math>SVP_\gamma</math> и <math>CVP_\gamma</math> для коэффициентов аппроксимации <math>\gamma = n^c</math>, полиномиальных относительно ранга решетки. А именно:

Существует теоретическое доказательство того, что для больших полиномиальных коэффициентов <math>\gamma = n^c</math> задачи <math>SVP_\gamma</math> и <math>CVP_\gamma</math> не являются NP-трудными. В частности, обе задачи принадлежат к классу сложности со AM для коэффициента аппроксимации <math>\gamma = O(\sqrt{n/log \; n})</math> (см. [12, гл. 9]). Таким образом, эти задачи не могут быть NP-трудными в пределах таких коэффициентов, если только не нарушается полиномиальная иерархия классов сложности.