הצגת המקור של הדף "בעיית הווקטור הקרוב ביותר"

{{מקורות|רמה=מחפש|נושא=מדעי הטבע}}
ב[[מתמטיקה]], ובפרט ב[[מדעי המחשב]], '''בעיית הווקטור הקרוב ביותר''' היא [[בעיה NP-שלמה]] אשר משמשת ב[[הצפנה]] וב[[רדוקציה חישובית|רדוקציה]] של בעיות.

שימוש מהותי של בעיה זו הוא ב[[פרוטוקול]] ההצפנה [[GGH]]. בעיה זו היא בעיית הסריג המפורסמת ביותר.

== הגדרות ==
בהינתן קבוצה של <math>n</math> [[מרחב וקטורי|וקטורים]] בלתי תלויים מעל <math>\mathbb{R}^n</math>:
* '''סריג''' (Lattice) <math>L</math> ה[[קבוצה פורשת|נפרש]] על ידי <math>B=\{\mathbf{b}_1,\mathbf{b}_2,...,\mathbf{b}_n\}</math> הוא קבוצת כל ה[[צירוף ליניארי|צירופים הליניאריים]] האפשריים של הווקטורים <math>\mathbf{b}_i</math> עם מקדמים [[מספר שלם|שלמים]], כלומר:<math>\mathcal{L}_B = \Biggl\{ \sum_{i=0}^{n}k_i\textbf{b}_i : k_i \in \mathbb{Z}\; \; \forall i \Biggr\}</math>, לעיתים נקרא לסריג זה '''הסריג שנוצר על ידי B'''
* נגדיר בנוסף את ה'''דטרמיננטה של הסריג''' להיות <math>Det(\mathcal{L}_B) = |det(B)|</math> כאשר det היא ה[[דטרמיננטה]] של קבוצת הווקטורים B.
* עבור סריג <math>\mathcal{L}</math> נגדיר את '''הסריג הדואלי''', שנסמנו <math>\mathcal{L}^*</math>, בתור האוסף הבא: <math>\mathcal{L}^* = \Biggl\{ x \in \mathbb{R}^n : y^Tx \in \mathbb{Z} \; \text{for all} \; y \in \mathcal{L} \Biggr\}</math>. טענה מרכזית היא להוכיח שאכן הסריג הדואלי הוא ה[[מרחב דואלי|מרחב הדואלי]] של הסריג המקורי.

== ניסוח פורמלי ==
בעיית הווקטור הקרוב ביותר: יהי <math>\mathcal{L} = \mathcal{L}_B</math> ומספר חיובי <math>0 < \lambda</math>. בעיית הווקטור המינימלי היא למצוא וקטור <math>b \in \mathcal{L}, b \neq 0</math> כך ש <math>\lVert b \rVert \leq \lambda</math>

[[קטגוריה:בעיות נודעות במתמטיקה]]

[[en:Closest vector problem]]