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

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

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

 הגדרות 
בהינתן קבוצה של  וקטורים בלתי תלויים מעל :
 סריג (Lattice)  הנפרש על ידי  הוא קבוצת כל הצירופים הליניאריים האפשריים של הווקטורים  עם מקדמים שלמים, כלומר:, לעיתים נקרא לסריג זה הסריג שנוצר על ידי B
 נגדיר בנוסף את הדטרמיננטה של הסריג להיות  כאשר det היא הדטרמיננטה של קבוצת הווקטורים B.
 עבור סריג  נגדיר את הסריג הדואלי, שנסמנו , בתור האוסף הבא: . טענה מרכזית היא להוכיח שאכן הסריג הדואלי הוא המרחב הדואלי של הסריג המקורי.

 ניסוח פורמלי 
בעיית הווקטור הקרוב ביותר: יהי  ומספר חיובי . בעיית הווקטור המינימלי היא למצוא וקטור  כך ש 

קטגוריה:בעיות נודעות במתמטיקה

en:Closest vector problem