Complexity classes as mathematical axioms

Abstract

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, ${\rm P}^{\# {\rm P}} \neq {\rm 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.

  • [Friedman] Go to document H. M. Friedman, "Finite functions and the necessary use of large cardinals," Ann. of Math., vol. 148, iss. 3, pp. 803-893, 1998.
    @article{Friedman,
      author = {Friedman, Harvey M.},
      TITLE = {Finite functions and the necessary use of large cardinals},
      JOURNAL = {Ann. of Math.},
      FJOURNAL = {Annals of Mathematics. Second Series},
      VOLUME = {148},
      YEAR = {1998},
      NUMBER = {3},
      PAGES = {803--893},
      ISSN = {0003-486X},
      CODEN = {ANMAAH},
      MRCLASS = {03E55 (03E15)},
      MRNUMBER = {2002b:03108},
      MRREVIEWER = {P. Matet},
      DOI = {10.2307/121032},
      ZBLNUMBER = {0941.03050},
      }
  • [Nabutovsky] 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.
    @article{Nabutovsky,
      author = {Nabutovsky, Alexander},
      TITLE = {Non-recursive functions, knots ``with thick ropes'', and self-clenching ``thick'' hyperspheres},
      JOURNAL = {Comm. Pure Appl. Math.},
      FJOURNAL = {Communications on Pure and Applied Mathematics},
      VOLUME = {48},
      YEAR = {1995},
      NUMBER = {4},
      PAGES = {381--428},
      ISSN = {0010-3640},
      CODEN = {CPAMA},
      MRCLASS = {58E15 (58E10 58E12 58E50)},
      MRNUMBER = {96d:58025},
      ZBLNUMBER = {0845.57023},
      }
  • [Thompson] A. Thompson, Private communication.
    @misc{Thompson,
      author = {Thompson, A.},
      TITLE = {Private communication},
      }
  • [FKLW] Go to document 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.
    @article{FKLW,
      author = {Freedman, Michael H. and Kitaev, Alexei and Larsen, Michael J. and Wang, Zhenghan},
      TITLE = {Topological quantum computation},
      JOURNAL = {Bull. Amer. Math. Soc.},
      FJOURNAL = {American Mathematical Society. Bulletin. New Series},
      VOLUME = {40},
      YEAR = {2003},
      NUMBER = {1},
      PAGES = {31--38},
      ISSN = {0273-0979},
      CODEN = {BAMOAD},
      MRCLASS = {57R56 (68Q05 81P68)},
      MRNUMBER = {2003m:57065},
      DOI = {10.1090/S0273-0979-02-00964-3},
      ZBLNUMBER = {1019.81008},
      }
  • [RT] Go to document 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.
    @article{RT,
      author = {Turaev, V. G. and Reshetikhin, N.},
      TITLE = {Invariants of {$3$}-manifolds via link polynomials and quantum groups},
      JOURNAL = {Invent. Math.},
      FJOURNAL = {Inventiones Mathematicae},
      VOLUME = {103},
      YEAR = {1991},
      NUMBER = {3},
      PAGES = {547--597},
      ISSN = {0020-9910},
      CODEN = {INVMBH},
      MRCLASS = {57N10 (17B37 57M25 81R50)},
      MRNUMBER = {92b:57024},
      MRREVIEWER = {Louis H. Kauffman},
      DOI = {10.1007/BF01239527},
      ZBLNUMBER = {0725.57007},
      }
  • [JVW] Go to document 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.
    @article{JVW,
      author = {Jaeger, F. and Vertigan, D. L. and Welsh, D. J. A.},
      TITLE = {On the computational complexity of the {J}ones and {T}utte polynomials},
      JOURNAL = {Math. Proc. Cambridge Philos. Soc.},
      FJOURNAL = {Mathematical Proceedings of the Cambridge Philosophical Society},
      VOLUME = {108},
      YEAR = {1990},
      NUMBER = {1},
      PAGES = {35--53},
      ISSN = {0305-0041},
      CODEN = {MPCPCO},
      MRCLASS = {05B35 (57M25 68Q25)},
      MRNUMBER = {91h:05038},
      MRREVIEWER = {Mark E. Kidwell},
      DOI = {10.1017/S0305004100068936},
      ZBLNUMBER = {0747.57006},
      }
  • [Papa] C. H. Papadimitriou, Computational Complexity, Reading, MA: Addison-Wesley Publ. Co., 1994.
    @book{Papa,
      author = {Papadimitriou, Christos H.},
      TITLE = {Computational {C}omplexity},
      PUBLISHER = {Addison-Wesley Publ. Co.},
      ADDRESS = {Reading, MA},
      YEAR = {1994},
      PAGES = {xvi+523},
      ISBN = {0-201-53082-1},
      MRCLASS = {68Q15 (68-02 68Q25)},
      MRNUMBER = {95f:68082},
      MRREVIEWER = {Johan H{\aa}stad},
      ZBLNUMBER = {0833.68049},
      }
  • [Toda] 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.
    @article{Toda,
      author = {Toda, S.},
      TITLE = {On the computational power of PP and $\oplus@$P},
      JOURNAL = {Proc. 30th {\rm IEEE} Symposium on the Foundations of Computer Science},
      YEAR = {1989},
      PAGES = {514--519},
      }
  • [Berger] R. Berger, "The undecidability of the domino problem," Mem. Amer. Math. Soc. No., vol. 66, p. 72, 1966.
    @article {Berger,
      author = {Berger, Robert},
      TITLE = {The undecidability of the domino problem},
      JOURNAL = {Mem. Amer. Math. Soc. No.},
      FJOURNAL = {Memoirs of the American Mathematical Society},
      VOLUME = {66},
      YEAR = {1966},
      PAGES = {72},
      ISSN = {0065-9266},
      MRCLASS = {02.74},
      MRNUMBER = {36 \#49},
      MRREVIEWER = {J. R. B{ü}chi},
      ZBLNUMBER = {0199.30802},
      }
  • [Stillwell] Go to document J. Stillwell, "The word problem and the isomorphism problem for groups," Bull. Amer. Math. Soc., vol. 6, iss. 1, pp. 33-56, 1982.
    @article {Stillwell,
      author = {Stillwell, John},
      TITLE = {The word problem and the isomorphism problem for groups},
      JOURNAL = {Bull. Amer. Math. Soc.},
      FJOURNAL = {American Mathematical Society. Bulletin. New Series},
      VOLUME = {6},
      YEAR = {1982},
      NUMBER = {1},
      PAGES = {33--56},
      ISSN = {0273-0979},
      CODEN = {BAMOAD},
      MRCLASS = {20F10 (01A60 03D40)},
      MRNUMBER = {82m:20039},
      MRREVIEWER = {D. E. Cohen},
      DOI = {10.1090/S0273-0979-1982-14963-1},
      ZBLNUMBER = {0483.20018},
      }
  • [Turaev] V. G. Turaev, Quantum Invariants of Knots and 3-Manifolds, Berlin: Walter de Gruyter & Co., 1994.
    @book {Turaev,
      author = {Turaev, V. G.},
      TITLE = {Quantum Invariants of Knots and 3-Manifolds},
      SERIES = {de Gruyter Stud. Math.},
      NUMBER = {18},
      PUBLISHER = {Walter de Gruyter \& Co.},
      ADDRESS = {Berlin},
      YEAR = {1994},
      PAGES = {x+588},
      ISBN = {3-11-013704-6},
      MRCLASS = {57M25 (16W30 17B37 57N10 81R50)},
      MRNUMBER = {95k:57014},
      MRREVIEWER = {Louis H. Kauffman},
      ZBLNUMBER = {0812.57003},
      }
  • [Thistle] Go to document M. B. Thistlethwaite, "A spanning tree expansion of the Jones polynomial," Topology, vol. 26, iss. 3, pp. 297-309, 1987.
    @article {Thistle,
      author = {Thistlethwaite, Morwen B.},
      TITLE = {A spanning tree expansion of the {J}ones polynomial},
      JOURNAL = {Topology},
      FJOURNAL = {Topology. An International Journal of Mathematics},
      VOLUME = {26},
      YEAR = {1987},
      NUMBER = {3},
      PAGES = {297--309},
      ISSN = {0040-9383},
      CODEN = {TPLGAF},
      MRCLASS = {57M25},
      MRNUMBER = {88h:57007},
      MRREVIEWER = {G. Burde},
      DOI = {10.1016/0040-9383(87)90003-6},
      ZBLNUMBER = {0622.57003},
      }
  • [Vertigan1] Go to document D. Vertigan, "The computational complexity of Tutte invariants for planar graphs," SIAM J. Comput., vol. 35, iss. 3, pp. 690-712, 2005.
    @article {Vertigan1,
      author = {Vertigan, Dirk},
      TITLE = {The computational complexity of {T}utte invariants for planar graphs},
      JOURNAL = {{\rm SIAM} J. Comput.},
      FJOURNAL = {SIAM Journal on Computing},
      VOLUME = {35},
      YEAR = {2005},
      NUMBER = {3},
      PAGES = {690--712},
      ISSN = {0097-5397},
      MRCLASS = {68Q17 (05A15 05B35 05C85 68Q15 68Q25 68R10)},
      MRNUMBER = {2006k:68045},
      MRREVIEWER = {Mark R. Jerrum},
      DOI = {10.1137/S0097539704446797},
      ZBLNUMBER = {1089.05017},
      }
  • [Vertigan2] Vertigan, Dirk, The computational complexity of Tutte, Jones, Homfly and Kaufman invariants, 1991.
    @unpublished {Vertigan2,
      author = {Vertigan, Dirk},
      TITLE = {The computational complexity of {T}utte, {J}ones, {H}omfly and {K}aufman invariants},
      NOTE = {Ph.D. thesis, Oxford University, Oxford, England},
      YEAR = {1991},
      }
  • [Fox] R. H. Fox, "Congruence classes of knots," Osaka Math. J., vol. 10, pp. 37-41, 1958.
    @article {Fox,
      author = {Fox, R. H.},
      TITLE = {Congruence classes of knots},
      JOURNAL = {Osaka Math. J.},
      VOLUME = {10},
      YEAR = {1958},
      PAGES = {37--41},
      MRCLASS = {55.20},
      MRNUMBER = {24 \#A1718},
      MRREVIEWER = {Horst Schubert},
      ZBLNUMBER = {0084.19204},
      }
  • [Lackenby] Go to document 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.
    @article {Lackenby,
      author = {Lackenby, Marc},
      TITLE = {Fox's congruence classes and the quantum-{${\rm SU}(2)$} invariants of links in {$3$}-manifolds},
      JOURNAL = {Comment. Math. Helv.},
      FJOURNAL = {Commentarii Mathematici Helvetici},
      VOLUME = {71},
      YEAR = {1996},
      NUMBER = {4},
      PAGES = {664--677},
      ISSN = {0010-2571},
      CODEN = {COMHAX},
      MRCLASS = {57M25 (57N10 57R57)},
      MRNUMBER = {97m:57007},
      MRREVIEWER = {Justin D. Roberts},
      ZBLNUMBER = {0871.57003},
      DOI = {10.1007/BF02566441},
      }

Authors

Michael H. Freedman

Microsoft Corporation
CNSI Building, Rm. 2245
University of California
Santa Barbara, CA 93106-6105