בעיית הצמידות

בתורת החבורות, בעיית הצמידות היא בעיית הכרעה שבאה לקבוע האם שני איברים בחבורה בעלת הצגה הם צמודים. בעיה זו ובעיות דומות נוספות באות לידי ביטוי בעולם ההצפנה, והן מהסיבות לבטיחותם של פרוטוקולי הצפנה שונים.

הגדרה פורמלית

בהינתן חבורה G עם הצגה, בעיית הצמידות מוגדרת כך - בהינתן שני איברים x,y של G, האם קיים איבר c של G עבורו מתקיים $y={c}^{-1}xc$.

האיבר c נקרא המצמיד של x ו-y.

לבעיה זו יש משמעות רק בחבורות לא אבליות, משום שבחבורה אבלית מחלקות הצמידות היחידות הן היחידונים.

הקשר לבעיות אחרות

בתורת החבורות מספר בעיות מפורסמות דומות, ביניהן בעיית המילה. בעיית הצמידות קשורה לבעיית המילה ולמעשה מהווה תנאי מספיק עבורה - כדי לדעת האם שתי מילים w,v שקולות, מספיק לדעת האם ${w}^{-1}v$ צמודה לזהות.

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

בעיית צמידות החזקות (power conjugacy problem) שואלת (בהינתן חבורה מוצגת סופית ושני איברים בה) האם לאברים יש חזקות צמודות. בעיה זו אינה תלויה בבעיית הצמידות: יש חבורות שבהן בעיית הצמידות פתירה ובעיית צמידות החזקות אינה פתירה, ולהפך.

כריעות הבעיה

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

ובכל זאת, ישנן חבורות רבות עבורן הבעיה פתירה, ביניהן חבורה חופשית, חבורת הצמות, חבורה היפרבולית ועוד רבות.

היותה של הבעיה פתירה אין הכוונה שהיא פתירה בקלות - כלומר לחבורות שונות (כמו חבורת הצמות) קשה מאוד למצוא איבר מצמיד (אפילו מתת-חבורה נתונה), כלומר לבעיה סיבוכיות קשה.

הקשר להצפנה

לבעיה זו ולבעיות דומות מתורת החבורות יש קשר הדוק להצפנה ולבטיחות פרוטוקולי הצפנה שונים בחבורות לא קומוטטיביות. הקושי בפענוח צפנים טומן בתוכו את הקושי בפתרון בעיית הצמידות.

בחבורות בהן סיבוכיות בעיית הצמידות ובעיית חיפוש המצמיד קשה יש שימוש נרחב בפרוטוקולי הצפנה רבים, כמו בפרוטוקולים של Anshel–Anshel–Goldfeld ו-Ko–Lee et. al.

בעיית חיפוש המצמיד מכונה לעיתים בעיית לוגריתם בדיד, ובכך קושי פתירתה אנלוגי לקושי במציאת לוגריתם בדיד בחבורות אבליות, כמו בפרוטוקול דיפי-הלמן.

ראו גם

• הצמדה (תורת החבורות)
• הצגה על ידי יוצרים ויחסים