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

Основными вычислительными задачами на решетках являются ''задача о кратчайшем векторе'' (Shortest Vector Problem, SVP), в которой требуется найти кратчайший ненулевой вектор в данной решетке, и ''задача о ближайшем векторе'' (Closest Vector Problem, CVP), в которой требуется найти точку решетки, ближайшую к заданной цели. Обе задачи могут быть определены относительно любой нормы, но евклидова норма <math>\parallel \mathbf{v} \parallel = \sqrt {\sum_i v^2_i}</math> является наиболее распространенной. Также в приложениях вычислительных наук часто встречаются такие нормы, как норма <math>\ell_1: \parallel \mathbf{v} \parallel _1 = \sum_i |v_i| </math>, и норма <math>max: \parallel \mathbf{v} \parallel _\infty = max_i |v_i|</math>. Далее будет рассматриваться евклидова норма.

'''Определение 1 (Задача о кратчайшем векторе, <math>SVP_\gamma</math>)'''. Пусть дана решетка <math>\mathcal{L} (\mathbf{B})</math>. Требуется найти ненулевой вектор решетки <math>\mathbf{Bx}</math> (где <math>\mathbf{x} \in \mathbb{Z}^n \backslash \{ \mathbf{0} \}</math>), такой, что <math>\parallel \mathbf{Bx} \parallel \le \gamma \cdot \parallel \mathbf{By} \parallel </math> для любого <math>\mathbf{y} \in \mathbb{Z}^n \backslash \{ \mathbf{0} \}</math>.

'''Определение 2 (Задача о ближайшем векторе, <math>CVP_\gamma</math>)'''. Пусть даны решетка <math>\mathcal{L} (\mathbf{B})</math> и целевая точка <math>\mathbf{t}</math>. Требуется найти вектор решетки <math>\mathbf{Bx}</math> (где <math>\mathbf{x} \in \mathbb{Z}^n</math>), такой, что <math>\parallel \mathbf{Bx - t} \parallel \le \gamma \cdot \parallel \mathbf{By - t} \parallel </math> для любого <math>\mathbf{y} \in \mathbb{Z}^n</math>.