4551
правка
Задача о кратчайшем векторе: различия между версиями
Перейти к навигации
Перейти к поиску
м
Задача о кратчайшем векторе (посмотреть исходный код)
Версия от 18:52, 26 марта 2022
, 26 марта 2022→Постановка задачи
Irina (обсуждение | вклад) Нет описания правки |
Irina (обсуждение | вклад) |
||
| Строка 12: | Строка 12: | ||
'''Определение 1 (Задача о кратчайшем векторе, <math>SVP_\gamma</math>)'''. Пусть дана решетка <math>\mathcal{L} (\mathbf{B})</math>. Требуется найти ненулевой вектор решетки Bx (где x2Znnf0g), такой, что kBx k у ■ ||By|| для любого yeZ"\{0}. | '''Определение 1 (Задача о кратчайшем векторе, <math>SVP_\gamma</math>)'''. Пусть дана решетка <math>\mathcal{L} (\mathbf{B})</math>. Требуется найти ненулевой вектор решетки <math>\mathbf{Bx}</math> (где x2Znnf0g), такой, что kBx k у ■ ||By|| для любого yeZ"\{0}. | ||
''Определение 2 (Задача о ближайшем векторе, <math>CVP_\gamma</math>)''. Пусть даны решетка <math>\mathcal{L} (\mathbf{B})</math> и целевая точка t. Требуется найти вектор решетки Bx (где x 2 Zn) такой, что kBx - t k у - ||By - tk для любого y2Zn. | '''Определение 2 (Задача о ближайшем векторе, <math>CVP_\gamma</math>)'''. Пусть даны решетка <math>\mathcal{L} (\mathbf{B})</math> и целевая точка t. Требуется найти вектор решетки <math>\mathbf{Bx}</math> (где x 2 Zn) такой, что kBx - t k у - ||By - tk для любого y2Zn. | ||