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

Поскольку эффективные алгоритмы для точного решения SVP и CVP в произвольно высокой размерности неизвестны, эти задачи обычно определяются в их аппроксимационной версии, где коэффициент аппроксимации у > 1 может быть функцией размерности или ранга решетки.

Определение 1 (Задача о кратчайшем векторе, SVPy). Дана решетка L(B). Требуется найти ненулевой вектор решетки Bx (где x2Znnf0g), такой, что kBx k у ■ ||By|| для любого yeZ"\{0}.

Определение 2 (Задча о ближайшем векторе, CVPy). Пусть даны решетка L(B) и целевая точка t. Требуется найти вектор решетки Bx (где x 2 Zn) такой, что kBx - t k у - ||By - tk для любого y2Zn.