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

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

• Существуют ли алгоритмы с полиномиальным временем выполнения, которые решают задачу <math>SVP_\gamma</math> или <math>CVP_\gamma</math> для полиномиальных коэффициентов у = nc? (Нахождение таких алгоритмов даже для очень большой экспоненты c стало бы серьезным прорывом в вычислительных науках).

• Существует ли e > 0 такое, что аппроксимация <math>SVP_\gamma</math> или <math>CVP_\gamma</math> в пределах у = n€ является NP-трудной? (Самые сильные известные сведения о неаппроксимируемости [ ] относятся к коэффициентам вида nO(1/loglog n), которые растут быстрее любой полилогарифмической функции, но медленнее любой полиномиальной).

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