Citation: Freedman, Michael H. "Complexity classes as mathematical axioms." Annals of mathematics (2009): 995-1002.
Web: https://arxiv.org/abs/0810.0033
Tags: Philosophical
The premise of this paper is lovely and simple. There are some quite foundational problems in computational complexity; for instance, P!=NP. Seeing as computational problems are sometimes undecidable (e.g. Halting problem) one might guess that P!=NP could be undecidable in the sense that it is independent of ZFC. Thus, we might want to assume P!=NP or similar separation conjectures as axioms and use them to prove theorems.
This paper takes a first step in this direction. Mike assumes that P^#P (P with an oracle to a #P complete problem) is not equal to NP. From this he proves a result in knot theory, which says that generically it is not possible to start with a diagram for a link and produce exponential simplifications on that diagram by applying Dehn surgeries which preserve Jones polynomial evaluated at a root of unity r.
The proof goes by contradiction. Suppose that every link diagram could be exponentially simplified by such Dehn surgeries. Then, then simplification by Dehn surgery would be a certificate which demonstrates the evaluation of the Jones polynomial of the knot. Seeing as evaluating Jones polynomials at roots of unity is #P complete, this would prove that there is a certificate which demonstrates the solutions to #P-compelte problems. Thus, a #P oracle would be just as powerful as allowing certificates. That is, P^#P would be equal to NP. Thus, we get a contradiction! Hence, the separation axiom implies the theorem.
Interestingly, assuming a finer quantum complexity separation one can even show that weaker linear simplifications are impossible:
> Cui, Shawn X., Michael H. Freedman, and Zhenghan Wang. "Complexity classes as mathematical axioms II." Quantum Topology 7.1 (2016): 185-201.
Mike highlights the analogy between this work and Havery Friedman's work, where large cardinal axioms are assumed and used to deduce results in Ramsey theory:
> Friedman, Harvey M. "Finite functions and the necessary use of large cardinals." Annals of Mathematics (1998): 803-893.