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

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

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

הגדרות

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

• סריג (Lattice) $L$ הנפרש על ידי $B=\{{\mathbf{𝐛}}_1,{\mathbf{𝐛}}_2,...,{\mathbf{𝐛}}_n\}$ הוא קבוצת כל הצירופים הליניאריים האפשריים של הווקטורים ${\mathbf{𝐛}}_i$ עם מקדמים שלמים, כלומר:${{ℒ}}_B=\{\sum _{i=0}^n{k}_i{\text{b}}_i:k_i\in \mathbb{\mathbb{Z}}\mathrm{\forall }i\}$, לעיתים נקרא לסריג זה הסריג שנוצר על ידי B
• נגדיר בנוסף את הדטרמיננטה של הסריג להיות $Det({{ℒ}}_B)=|det(B)|$ כאשר det היא הדטרמיננטה של קבוצת הווקטורים B.
• עבור סריג ${ℒ}$ נגדיר את הסריג הדואלי, שנסמנו ${{ℒ}}^{*}$, בתור האוסף הבא: ${{ℒ}}^{*}=\{x\in {\mathbb{ℝ}}^n:y^{T}x\in \mathbb{\mathbb{Z}}\text{for all}y\in {ℒ}\}$. טענה מרכזית היא להוכיח שאכן הסריג הדואלי הוא המרחב הדואלי של הסריג המקורי.

ניסוח פורמלי

בעיית הווקטור הקרוב ביותר: יהי ${ℒ}={{ℒ}}_B$ ומספר חיובי $0<\lambda$. בעיית הווקטור המינימלי היא למצוא וקטור $b\in {ℒ},b\ne 0$ כך ש $\Vert b\Vert \le \lambda$

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

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