בעיית הווקטור הקרוב ביותר

במתמטיקה ובפרט במדעי המחשב. בעיית הווקטור הקרוב ביותר הא בעיה מסוג NP-complete) אשר משמשת בהצפנה וברדוקציה של בעיות.

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

הגדרות

בהינתן קבוצה של $n$ וקטורים בלתי תלויים מעל $\mathbb {R} ^{n}$:

• סריג (Lattice) $L$ הנפרש על ידי $B=\{\mathbf {b} _{1},\mathbf {b} _{2},...,\mathbf {b} _{n}\}$ הוא קבוצת כל הצירופים הליניאריים האפשריים של הווקטורים $\mathbf {b} _{i}$ עם מקדמים שלמים, כלומר:${\mathcal {L}}_{B}={\Biggl \{}\sum _{i=0}^{n}k_{i}{\textbf {b}}_{i}:k_{i}\in \mathbb {Z} \;\;\forall i{\Biggr \}}$, לעיתים נקרא לסריג זה הסריג שנוצר על ידי B
• נגדיר בנוסף את הדיטרמיננטה של הסריג להיות $Det({\mathcal {L}}_{B})=|det(B)|$ כאשר det היא הדיטרמיננטה של קבוצת הווקטורים B.
• עבור סריג ${\mathcal {L}}$ נגדיר את הסריג הדואלי שנסמנו ${\mathcal {L}}^{*}$ שנגדירו בתור האוסף הבא: ${\mathcal {L}}^{*}={\Biggl \{}x\in \mathbb {R} ^{n}:y^{T}x\in \mathbb {Z} \;{\text{for all}}\;y\in {\mathcal {L}}{\Biggr \}}$. טענה מרכזית היא להוכיח שאכן הסריג הדואלי הוא המרחב הדואלי של הסריג המקורי.

ניסוח פורמלי

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

הערך באדיבות ויקיפדיה העברית, קרדיט,
רשימת התורמים
רישיון cc-by-sa 3.0

35556054בעיית הווקטור הקרוב ביותר