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

''Точечная решетка'' представляет собой множество всех целочисленных линейных комбинаций <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> (называемой ''базисом'') с порождающими векторами в качестве столбцов. Используя матричную нотацию, точки решетки в L(B) удобно представить в виде Bx, где x – целочисленный вектор. Целые числа m и n называются размерностью и рангом решетки, соответственно. Заметим, что любая решетка допускает несколько базисов, но все они имеют одинаковые ранг и размерность.

Основными вычислительными задачами на решетках являются задача о кратчайшем векторе (Shortest Vector Problem, SVP), в которой требуется найти кратчайший ненулевой вектор в данной решетке, и задача о ближайшем векторе (Closest Vector Problem, CVP), в которой требуется найти точку решетки, ближайшую к заданной цели. Обе задачи могут быть определены относительно любой нормы, но евклидова норма kvk = Pi v2i является наиболее распространенной. Также в приложениях вычислительных наук часто встречаются такие нормы, как l\ норма kvk1 = Pi jvij и max норма KVK1 = maxi j v i j. Далее будет рассматриваться евклидова норма.