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

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

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

הגדרות

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

סריג (Lattice) $L$ הנפרש על ידי $B = {𝐛_{1}, 𝐛_{2}, ..., 𝐛_{n}}$ הוא קבוצת כל הצירופים הליניאריים האפשריים של הווקטורים $𝐛_{i}$ עם מקדמים שלמים, כלומר: $ℒ_{B} = {\sum_{i = 0}^{n} k_{i} 𝐛_{i} : k_{i} \in ℤ \forall i}$ , לעיתים נקרא לסריג זה הסריג שנוצר על ידי B
נגדיר בנוסף את הדטרמיננטה של הסריג להיות $D e t (ℒ_{B}) = | d e t (B) |$ כאשר det היא הדטרמיננטה של קבוצת הווקטורים B.
עבור סריג $ℒ$ נגדיר את הסריג הדואלי, שנסמנו $ℒ^{*}$ , בתור האוסף הבא: $ℒ^{*} = {x \in ℝ^{n} : y^{T} x \in ℤ for all y \in ℒ}$ . טענה מרכזית היא להוכיח שאכן הסריג הדואלי הוא המרחב הדואלי של הסריג המקורי.

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