Complexity classes as mathematical axioms

• 成果类型: Article
• 署名作者: Freedman, Michael H.
• 刊物名称: ANNALS OF MATHEMATICS
• ISSN/ISSBN: 0003-486X
• DOI: 10.4007/annals.2009.170.995
• 发表日期: 2009
• 页码: 995-1002
• 关键词: jones

摘要

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, P-#P not equal 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.