Complexity classes as mathematical axioms. (English) Zbl 1178.03069

Summary: Complexity theory, being the metrical version of decision theory, has long been suspected of harboring undecidable statements among its most prominent conjectures. Taking this possibility seriously, we add one such conjecture, \(\text{P}^{\#\text{P}}\neq \text{NP}\), as a new “axiom” and find that it has an implication in 3-dimensional topology. This is reminiscent of Harvey Friedman’s work on finitistic interpretations of large cardinal axioms.


03E65 Other set-theoretic hypotheses and axioms
57M25 Knots and links in the \(3\)-sphere (MSC2010)
68Q15 Complexity classes (hierarchies, relations among complexity classes, etc.)
Full Text: DOI Link


[1] H. M. Friedman, ”Finite functions and the necessary use of large cardinals,” Ann. of Math., vol. 148, iss. 3, pp. 803-893, 1998. · Zbl 0941.03050 · doi:10.2307/121032
[2] A. Nabutovsky, ”Non-recursive functions, knots “with thick ropes”, and self-clenching “thick” hyperspheres,” Comm. Pure Appl. Math., vol. 48, iss. 4, pp. 381-428, 1995. · Zbl 0845.57023 · doi:10.1002/cpa.3160480402
[3] A. Thompson, Private communication.
[4] M. H. Freedman, A. Kitaev, M. J. Larsen, and Z. Wang, ”Topological quantum computation,” Bull. Amer. Math. Soc., vol. 40, iss. 1, pp. 31-38, 2003. · Zbl 1019.81008 · doi:10.1090/S0273-0979-02-00964-3
[5] V. G. Turaev and N. Reshetikhin, ”Invariants of \(3\)-manifolds via link polynomials and quantum groups,” Invent. Math., vol. 103, iss. 3, pp. 547-597, 1991. · Zbl 0725.57007 · doi:10.1007/BF01239527
[6] F. Jaeger, D. L. Vertigan, and D. J. A. Welsh, ”On the computational complexity of the Jones and Tutte polynomials,” Math. Proc. Cambridge Philos. Soc., vol. 108, iss. 1, pp. 35-53, 1990. · Zbl 0747.57006 · doi:10.1017/S0305004100068936
[7] C. H. Papadimitriou, Computational Complexity, Reading, MA: Addison-Wesley Publ. Co., 1994. · Zbl 0833.68049
[8] S. Toda, ”On the computational power of PP and \(\oplus@\)P,” Proc. 30th IEEE Symposium on the Foundations of Computer Science, pp. 514-519, 1989.
[9] R. Berger, ”The undecidability of the domino problem,” Mem. Amer. Math. Soc. No., vol. 66, p. 72, 1966. · Zbl 0199.30802
[10] J. Stillwell, ”The word problem and the isomorphism problem for groups,” Bull. Amer. Math. Soc., vol. 6, iss. 1, pp. 33-56, 1982. · Zbl 0483.20018 · doi:10.1090/S0273-0979-1982-14963-1
[11] V. G. Turaev, Quantum Invariants of Knots and 3-Manifolds, Berlin: Walter de Gruyter & Co., 1994. · Zbl 0812.57003
[12] M. B. Thistlethwaite, ”A spanning tree expansion of the Jones polynomial,” Topology, vol. 26, iss. 3, pp. 297-309, 1987. · Zbl 0622.57003 · doi:10.1016/0040-9383(87)90003-6
[13] D. Vertigan, ”The computational complexity of Tutte invariants for planar graphs,” SIAM J. Comput., vol. 35, iss. 3, pp. 690-712, 2005. · Zbl 1089.05017 · doi:10.1137/S0097539704446797
[14] Vertigan, Dirk, The computational complexity of Tutte, Jones, Homfly and Kaufman invariants, 1991. · Zbl 1089.05017
[15] R. H. Fox, ”Congruence classes of knots,” Osaka Math. J., vol. 10, pp. 37-41, 1958. · Zbl 0084.19204
[16] M. Lackenby, ”Fox’s congruence classes and the quantum-\({ SU}(2)\) invariants of links in \(3\)-manifolds,” Comment. Math. Helv., vol. 71, iss. 4, pp. 664-677, 1996. · Zbl 0871.57003 · doi:10.1007/BF02566441
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.