בעיית הצמידות
בתורת החבורות, בעיית הצמידות היא בעיית הכרעה שבאה לקבוע האם שני איברים בחבורה בעלת הצגה הם צמודים. בעיה זו ובעיות דומות נוספות באות לידי ביטוי בעולם ההצפנה, והן מהסיבות לבטיחותם של פרוטוקולי הצפנה שונים.
הגדרה פורמלית
בהינתן חבורה G עם הצגה, בעיית הצמידות מוגדרת כך - בהינתן שני איברים x,y של G, האם קיים איבר c של G עבורו מתקיים .
האיבר c נקרא המצמיד של x ו-y.
לבעיה זו יש משמעות רק בחבורות לא אבליות, משום שבחבורה אבלית מחלקות הצמידות היחידות הן היחידונים.
הקשר לבעיות אחרות
בתורת החבורות מספר בעיות מפורסמות דומות, ביניהן בעיית המילה. בעיית הצמידות קשורה לבעיית המילה ולמעשה מהווה תנאי מספיק עבורה - כדי לדעת האם שתי מילים w,v שקולות, מספיק לדעת האם צמודה לזהות.
בעיה נוספת שנובעת ישירות מבעיה זו, היא בעיית חיפוש המצמיד, שמטרתה לא רק לקבוע האם קיים מצמיד, אלא גם למצוא אותו.
כריעות הבעיה
עולה השאלה הטבעית, האם תמיד אפשר לפתור את הבעיה, כלומר האם בכל חבורה נוצרת סופית אפשר לקבוע האם כל שני איבריה צמודים. התשובה לכך היא שלילית, כלומר עבור חבורות רבות הבעיה היא לא כריעה.
ובכל זאת, ישנן חבורות רבות עבורן הבעיה פתירה, ביניהן חבורה חופשית, חבורת הצמות, חבורה היפרבולית ועוד רבות.
היותה של הבעיה פתירה אין הכוונה שהיא פתירה בקלות - כלומר לחבורות שונות (כמו חבורת הצמות) קשה מאד למצוא איבר מצמיד (אפילו מתת-חבורה נתונה), כלומר לבעיה סיבוכיות קשה.
הקשר להצפנה
לבעיה זו ולבעיות דומות מתורת החבורות יש קשר הדוק להצפנה ולבטיחות פרוטוקולי הצפנה שונים בחבורות לא קומוטטיביות. הקושי בפענוח צפנים טומן בתוכו את הקושי בפתרון בעיית הצמידות.
בחבורות בהן סיבוכיות בעיית הצמידות ובעיית חיפוש המצמיד קשה יש שימוש נרחב בפרוטוקולי הצפנה רבים, כמו בפרוטוקולים של Anshel-Anshel-Goldfeld,Ko, Lee, et. al.
בעיית חיפוש המצמיד מכונה לעיתים בעיית לוגריתם דיסקרטי, ובכך קושי פתירתה אנלוגי לקושי במציאת לוגריתם דיסקרטי בחבורות אבליות, כמו בפרוטוקול דיפי-הלמן.