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

שגיאות פרמטריות בתבנית:מקורות
פרמטרי חובה [ נושא ] חסרים

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

שימוש מהותי של בעיה זו הוא בפרוטוקול ההצפנה 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$