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

''Точечная решетка'' представляет собой множество всех целочисленных линейных комбинаций <math>\mathcal{L} (\mathbf{b}_1, ..., \mathbf{b}_n) = \Bigg\{ \sum_{i = 1}^n x_i \mathbf{b}_i : x_1, ..., x_n \in \mathbb{Z} \Bigg\}</math> из n линейно независимых векторов <math>\mathbf{b}_1, ..., \mathbf{b}_n \in \mathbb{R}^m</math> в m-мерном евклидовом пространстве. Для удобства вычислений векторы решетки <math>\mathbf{b}_1, ..., \mathbf{b}_n</math> часто предполагаются целыми (или рациональными), так что решетка может быть представлена целочисленной матрицей <math>\mathbf{B} = [\mathbf{b}_1, ..., \mathbf{b}_n] \in \mathbb{R}^{m \times n}</math> (называемой ''базисом'') с порождающими векторами в качестве столбцов. Используя матричную нотацию, точки решетки в <math>\mathcal{L} (\mathbf{B})</math> удобно представить в виде <math>\mathbf{Bx}</math>, где <math>\mathbf{x}</math> – целочисленный вектор. Целые числа ''m'' и ''n'' называются ''размерностью'' и ''рангом'' решетки, соответственно. Заметим, что любая решетка допускает несколько базисов, но все они имеют одинаковые ранг и размерность.

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