בעיית ההתרה

שמאל|ממוזער| דיאגרמה מורכבת ומעט מבלבלת שכן היא נראית כקשר אך בפועל אין קשר ממשי, אלא המצב הוא "מותר" מאת מורוון ת'יסטלת'וייט
בעיית ההתרה (באנגלית: Unknotting problem) במתמטיקה היא הבעיה של מציאת אלגוריתם שבהינתן מערכת שהיא ייצוג כלשהו של קשר, למשל, בתרשים קשר, ידע לזהות מצב שבו אין בפועל "קשר", הוא המצב שנקרא "מותר" (באנגלית unknot).

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

 סיבוכיות חישובית 
צעדים ראשונים לקראת קביעת סיבוכיות בוצעו להוכיח שהבעיה היא במחלקות סיבוכיות מסדר גבוה, אשר מכילות את P. באמצעות משטחים רגילים לתאר את משטחי זייפרט של קשר נתון, הראו האס, לגריאס ופיפנגר (Hass, Lagarias & Pippenger) בשנת 1999 כי בעיית ההתרה שייכת למחלקת הסיבוכיות NP. בשנת 2005 טענו הרה טאני וימאמוטו (Hara, Tani & Yamamoto) כי בעיית ההתרה שייכת ל-AM ∩ co-AM, אולם מאוחר יותר הם חזרו בהם מטענה זו. בשנת 2011, גרג קופרברג הוכיח כי (בהנחת נכונות של השערת רימן הכללית) בעיית ההתרה היא ב-co-NP, ובשנת 2016, מארק לקנבי סיפק הוכחה ללא תנאי לחברות ב-co-NP.

לבעיית ההתרה יש את אותה סיבוכיות חישובית כמו בדיקה אם הטמעה של גרף לא מכוון במרחב האוקלידי הוא חסר קישורים.Lackenby, 2016

אחד מהקשרים של אוצ'יאיי הכולל 139 קודקודים, למשל, במקור "הותר" על ידי תוכנת מחשב תוך 108 שעות, אך הזמן הזה צומצם במחקרים עדכניים יותר ל-10 דקות.Ladd, Kavraki, 2004

 אלגוריתמי התרה 

 לקריאה נוספת 


















 הערות שוליים 

קטגוריה:בעיות חישוביות
קטגוריה:תורת הקשרים
התרה