×

Knottedness is in NP, modulo GRH. (English) Zbl 1358.68138

Summary: Given a tame knot \(K\) presented in the form of a knot diagram, we show that the problem of determining whether \( K\) is knotted is in the complexity class \(\mathsf {NP}\), assuming the generalized Riemann hypothesis (GRH). In other words, there exists a polynomial-length certificate that can be verified in polynomial time to prove that \( K\) is non-trivial. GRH is not needed to believe the certificate, but only to find a short certificate. This result complements the result of J. Hass et al. [J. ACM 46, No. 2, 185–211 (1999; Zbl 1065.68667)] that unknottedness is in \(\mathsf {NP}\). Our proof is a corollary of major results of others in algebraic geometry and geometric topology.

MSC:

68Q25 Analysis of algorithms and problem complexity
11M26 Nonreal zeros of \(\zeta (s)\) and \(L(s, \chi)\); Riemann and other hypotheses
57M25 Knots and links in the \(3\)-sphere (MSC2010)

Citations:

Zbl 1065.68667

Software:

ECPP
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Agol, I., Thurston norm is polynomial time certifiable (2002)
[2] Agrawal, M.; Kayal, N.; Saxena, N., PRIMES is in \(P\), Ann. of Math. (2), 160, 2, 781-793 (2004) · Zbl 1071.11070
[3] Aharonov, D.; Jones, V.; Landau, Z., A polynomial quantum algorithm for approximating the Jones polynomial, Algorithmica, 55, 3, 395-421 (2009) · Zbl 1191.68313
[4] Atkin, A. O.L.; Morain, F., Elliptic curves and primality proving, Math. Comp., 61, 203, 29-68 (1993) · Zbl 0792.11056
[5] Babai, L.; Moran, S., Arthur-Merlin games: a randomized proof system, and a hierarchy of complexity classes, J. Comput. System Sci., 36, 2, 254-276 (1988) · Zbl 0652.03029
[6] Bou-Rabee, K., Quantifying residual finiteness, J. Algebra, 323, 3, 729-737 (2010) · Zbl 1222.20020
[7] Bou-Rabee, K.; McReynolds, D. B., Extremal behavior of divisibility functions · Zbl 1314.20023
[8] Brassard, G., A note on the complexity of cryptography, IEEE Trans. Inform. Theory, 25, 2, 232-233 (1979) · Zbl 0393.68052
[9] Broaddus, N., Noncyclic covers of knot complements, Geom. Dedicata, 111, 211-239 (2005) · Zbl 1076.57006
[10] Freedman, M. H.; Kitaev, A.; Wang, Z., Simulation of topological field theories by quantum computers, Comm. Math. Phys., 227, 3, 587-603 (2002) · Zbl 1014.81006
[11] Goldreich, O.; Micali, S.; Wigderson, A., Proofs that yield nothing but their validity, or All languages in NP have zero-knowledge proof systems, J. Assoc. Comput. Mach., 38, 3, 691-729 (1991) · Zbl 0799.68101
[12] Goldwasser, S.; Kilian, J., Primality testing using elliptic curves, J. ACM, 46, 4, 450-472 (1999) · Zbl 1064.11503
[13] Goldwasser, S.; Sipser, M., Private coins versus public coins in interactive proof systems, (Proceedings of the Eighteenth Annual ACM Symposium on Theory of Computing, STOC’86 (1986), ACM), 59-68
[14] Haken, W., Theorie der Normalflächen, Acta Math., 105, 245-375 (1961) · Zbl 0100.19402
[16] Hara, M.; Tani, S.; Yamamoto, M., Unknotting is in \(AM \cap coAM\), (Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms (2005), ACM), 359-364, (electronic) · Zbl 1297.68093
[17] Hass, J.; Lagarias, J. C.; Pippenger, N., The computational complexity of knot and link problems, J. ACM, 46, 2, 185-211 (1999) · Zbl 1065.68667
[18] Hempel, J., Residual finiteness for 3-manifolds, (Combinatorial Group Theory and Topology. Combinatorial Group Theory and Topology, Alta, UT, 1984. Combinatorial Group Theory and Topology. Combinatorial Group Theory and Topology, Alta, UT, 1984, Ann. of Math. Stud., vol. 111 (1987), Princeton Univ. Press), 379-396 · Zbl 0772.57002
[19] Koiran, P., Hilbert’s Nullstellensatz is in the polynomial hierarchy, J. Complexity, 12, 4, 273-286 (1996), DIMACS TR 96-27. Special issue for FOCM 1997 · Zbl 0862.68053
[20] Kronheimer, P.; Mrowka, T., Dehn surgery, the fundamental group and \(SU(2)\), Math. Res. Lett., 11, 5-6, 741-754 (2004) · Zbl 1084.57006
[21] Kuperberg, G., How hard is it to approximate the Jones polynomial?, Theory Comput. (2014), in press
[23] Lagarias, J. C.; Odlyzko, A. M., Effective versions of the Chebotarev density theorem, (Algebraic Number Fields: \(L\)-Functions And Galois Properties. Algebraic Number Fields: \(L\)-Functions And Galois Properties, Proc. Sympos., Univ. Durham, 1975 (1977), Academic Press), 409-464
[24] Mal’cev, A. I., On the faithful representation of infinite groups by matrices, Amer. Math. Soc. Transl. (2), 45, 1-18 (1965) · Zbl 0158.02905
[25] Miller, G. L., Riemann’s hypothesis and tests for primality, J. Comput. System Sci., 13, 3, 300-317 (1976) · Zbl 0349.68025
[26] Musick, C., Recognizing trivial links in polynomial time, withdrawn in version 3
[27] Okamoto, T., On relationships between statistical zero-knowledge proofs, J. Comput. System Sci., 60, 1, 47-108 (2000) · Zbl 0956.68020
[28] Pratt, V. R., Every prime has a succinct certificate, SIAM J. Comput., 4, 3, 214-220 (1975) · Zbl 0316.68031
[29] Rabin, M. O., Probabilistic algorithm for testing primality, J. Number Theory, 12, 1, 128-138 (1980) · Zbl 0426.10006
[30] Weinberger, P. J., Finding the number of factors of a polynomial, J. Algorithms, 5, 2, 180-186 (1984) · Zbl 0542.12001
[31] Welsh, D. J.A., The complexity of knots, Quo vadis, graph theory?, Ann. Discrete Math., vol. 55, 159-171 (1993), North-Holland
[32] The Complexity Zoo
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.