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.

Authors

Michael H. Freedman

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