ערך מחפש מקורות
	רובו של ערך זה אינו כולל מקורות או הערות שוליים, וככל הנראה, הקיימים אינם מספקים. אנא עזרו לשפר את אמינות הערך באמצעות הבאת מקורות לדברים ושילובם בגוף הערך בצורת קישורים חיצוניים והערות שוליים. אם אתם סבורים כי ניתן להסיר את התבנית, ניתן לציין זאת בדף השיחה.

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

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

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

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

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