בעיית ההתרה
 |
בעיות פתוחות במתמטיקה: |
במתמטיקה, בעיית ההתרה (באנגלית: 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
