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

Основной открытой задачей в вычислительном исследовании решеток является определение сложности приближенных алгоритмов <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-трудными в пределах таких коэффициентов, если только не нарушается полиномиальная иерархия классов сложности.