בעיית ההתרה

בעיות פתוחות במתמטיקה:

האם קיים אלגוריתם התרת קשר בסיבוכיות פולינומית?
(בעיות פתוחות נוספות במתמטיקה)

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

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

סיבוכיות חישובית

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

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

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

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

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

לקריאה נוספת

Bar-Natan, Dror (2007), "Fast Khovanov homology computations", Journal of Knot Theory and Its Ramifications, 16 (3): 243–255, arXiv:math.GT/0606318, doi:10.1142/S0218216507005294, MR 2320156
Birman, Joan S.; Hirsch, Michael (1998), "A new algorithm for recognizing the unknot", Geometry and Topology, 2: 178–220, arXiv:math/9801126, doi:10.2140/gt.1998.2.175
Burton, Benjamin A. (2011a), "Maximal admissible faces and asymptotic bounds for the normal surface solution space" (PDF), Journal of Combinatorial Theory, Series A, 118 (4): 1410–1435, arXiv:1004.2605, doi:10.1016/j.jcta.2010.12.011, MR 2763065
Burton, Benjamin (2011b), "The Pachner graph and the simplification of 3-sphere triangulations", Proc. 27th ACM Symposium on Computational Geometry, pp. 153–162, arXiv:1011.4169, doi:10.1145/1998196.1998220
Dynnikov, Ivan (2006), "Arc-presentations of links: monotonic simplification", Fundamenta Mathematicae, 190: 29–76, arXiv:math/0208153, doi:10.4064/fm190-0-3
Haken, Wolfgang (1961), "Theorie der Normalflächen", Acta Mathematica, 105: 245–375, doi:10.1007/BF02559591
Hara, Masao; Tani, Seiichi; Yamamoto, Makoto (2005), "Unknotting is in AM ∩ co-AM", Proc. 16th ACM-SIAM Symposium on Discrete algorithms (SODA '05), pp. 359–364
Hass, Joel; Lagarias, Jeffrey C.; Pippenger, Nicholas (1999), "The computational complexity of knot and link problems", Journal of the ACM, 46 (2): 185–211, arXiv:math/9807016, doi:10.1145/301970.301971, MR 1693203
Hass, Joel; Lagarias, Jeffrey C. (2001), "The number of Reidemeister moves needed for unknotting", Journal of the American Mathematical Society, 14 (2): 399–428, arXiv:math/9807012, doi:10.1090/S0894-0347-01-00358-7, MR 1815217
Kawarabayashi, Ken-ichi; Kreutzer, Stephan; Mohar, Bojan (2010), "Linkless and flat embeddings in 3-space and the unknot problem" (PDF), Proc. ACM Symposium on Computational Geometry (SoCG '10), pp. 97–106, doi:10.1145/1810959.1810975
Kronheimer, Peter; Mrowka, Tomasz (2011), "Khovanov homology is an unknot-detector", Publications Mathématiques de l'IHÉS, 113 (1): 97–208, arXiv:1005.4346, doi:10.1007/s10240-010-0030-y
Kuperberg, Greg (2014), "Knottedness is in NP, modulo GRH", Advances in Mathematics, 256: 493–506, arXiv:1112.0845, doi:10.1016/j.aim.2014.01.007, MR 3177300
Lackenby, Marc (2015), "A polynomial upper bound on Reidemeister moves", Annals of Mathematics, Second Series, 182 (2): 491–564, arXiv:1302.0180, doi:10.4007/annals.2015.182.2.3, MR 3418524
Lackenby, Marc (2016), The efficient certification of Knottedness and Thurston norm, arXiv:1604.00290, Bibcode:2016arXiv160400290L
Ladd, Andrew M.; Kavraki, Lydia E. (2004), "Motion planning for knot untangling" (PDF), in Boissonnat, Jean-Daniel; Burdick, Joel; Goldberg, Ken; Hutchinson, Seth (eds.), Algorithmic Foundations of Robotics V, Springer Tracts in Advanced Robotics, vol. 7, Springer, pp. 7–23, doi:10.1007/978-3-540-45058-0_2
Manolescu, Ciprian; Ozsváth, Peter S.; Sarkar, Sucharit (2009), "A combinatorial description of knot Floer homology", Annals of Mathematics, Second Series, 169 (2): 633–660, arXiv:math/0607691, Bibcode:2006math......7691M, doi:10.4007/annals.2009.169.633, MR 2480614
Mijatović, Aleksandar (2005), "Simplical structures of knot complements", Mathematical Research Letters, 12 (6): 843–856, arXiv:math/0306117, doi:10.4310/mrl.2005.v12.n6.a6, MR 2189244

הערות שוליים

^ Lackenby, 2016
^ Ochiai, M. (1990). "Non-Trivial Projections of the Trivial Knot" (PDF). S.M.F. Asterisque. 192: 7–9.
^ Grzeszczuk, R.; Huang, M.; Kauffman, L. (1997). "Physically-based stochastic simplification of mathematical knots". IEEE Transactions on Visualization and Computer Graphics. 3 (3): 262–278. doi:10.1109/2945.620492.
^ Ladd, Kavraki, 2004

[1] Lackenby, 2016

[2] Ochiai, M. (1990). "Non-Trivial Projections of the Trivial Knot" (PDF). S.M.F. Asterisque. 192: 7–9.

[3] Grzeszczuk, R.; Huang, M.; Kauffman, L. (1997). "Physically-based stochastic simplification of mathematical knots". IEEE Transactions on Visualization and Computer Graphics. 3 (3): 262–278. doi:10.1109/2945.620492.

[4] Ladd, Kavraki, 2004

[1]

[2]

[3]

[4]