בעיית ההתרה

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

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

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

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

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

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

לקריאה נוספת

הערות שוליים 

בעיות חישוביות
תורת הקשרים
התרה