4551
правка
Задача о кратчайшем векторе: различия между версиями
Материал из WEGA
Задача о кратчайшем векторе (посмотреть исходный код)
Версия от 22:22, 26 марта 2022
, 26 марта 2022→Открытые вопросы
Irina (обсуждение | вклад) м (→Применение) |
Irina (обсуждение | вклад) |
||
| Строка 54: | Строка 54: | ||
== Открытые вопросы == | == Открытые вопросы == | ||
Основной открытой задачей в вычислительном исследовании решеток является определение сложности приближенных алгоритмов <math>SVP_\gamma</math> и <math>CVP_\gamma</math> для коэффициентов аппроксимации | Основной открытой задачей в вычислительном исследовании решеток является определение сложности приближенных алгоритмов <math>SVP_\gamma</math> и <math>CVP_\gamma</math> для коэффициентов аппроксимации <math>\gamma = n^c</math>, полиномиальных относительно ранга решетки. А именно: | ||
• Существуют ли алгоритмы с полиномиальным временем выполнения, которые решают задачу <math>SVP_\gamma</math> или <math>CVP_\gamma</math> для полиномиальных коэффициентов | • Существуют ли алгоритмы с полиномиальным временем выполнения, которые решают задачу <math>SVP_\gamma</math> или <math>CVP_\gamma</math> для полиномиальных коэффициентов <math>\gamma = n^c</math>? (Нахождение таких алгоритмов даже для очень большой экспоненты ''c'' стало бы серьезным прорывом в вычислительных науках). | ||
• Существует ли | • Существует ли <math>\epsilon > 0</math>, такое, что аппроксимация <math>SVP_\gamma</math> или <math>CVP_\gamma</math> в пределах <math>\gamma = n^{\epsilon}</math> является NP-трудной? (Самые сильные известные сведения о неаппроксимируемости [4] относятся к коэффициентам вида <math>n^{O(1 / log \; log \; n)}</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-трудными в пределах таких коэффициентов, если только не нарушается полиномиальная иерархия классов сложности. | ||
== Ссылка на код == | == Ссылка на код == | ||
