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