Geodesic
Complexity classes as mathematical axioms
Michael H. Freedman1
1Microsoft Corporation<br/>CNSI Building, Rm. 2245<br/>University of California<br/>Santa Barbara, CA 93106-6105
Annals of mathematics, Tome 170 (2009) no. 2, pp. 995-1002
Cet article a éte moissonné depuis la source Annals of Mathematics website

Voir la notice de l'article

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.

DOI : 10.4007/annals.2009.170.995

Michael H. Freedman  1

1 Microsoft Corporation<br/>CNSI Building, Rm. 2245<br/>University of California<br/>Santa Barbara, CA 93106-6105 
@article{10_4007_annals_2009_170_995,
     author = {Michael H. Freedman},
     title = {Complexity classes as mathematical axioms},
     journal = {Annals of mathematics},
     pages = {995--1002},
     year = {2009},
     volume = {170},
     number = {2},
     doi = {10.4007/annals.2009.170.995},
     mrnumber = {2552117
},
     zbl = {1178.03069},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.4007/annals.2009.170.995/}
}
TY  - JOUR
AU  - Michael H. Freedman
TI  - Complexity classes as mathematical axioms
JO  - Annals of mathematics
PY  - 2009
SP  - 995
EP  - 1002
VL  - 170
IS  - 2
UR  - http://geodesic.mathdoc.fr/articles/10.4007/annals.2009.170.995/
DO  - 10.4007/annals.2009.170.995
LA  - en
ID  - 10_4007_annals_2009_170_995
ER  - 
%0 Journal Article
%A Michael H. Freedman
%T Complexity classes as mathematical axioms
%J Annals of mathematics
%D 2009
%P 995-1002
%V 170
%N 2
%U http://geodesic.mathdoc.fr/articles/10.4007/annals.2009.170.995/
%R 10.4007/annals.2009.170.995
%G en
%F 10_4007_annals_2009_170_995
Michael H. Freedman. Complexity classes as mathematical axioms. Annals of mathematics, Tome 170 (2009) no. 2, pp. 995-1002. doi: 10.4007/annals.2009.170.995

Cité par Sources :