A note on da Costa-Doria ``exotic formalizations'' (Q711567)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | A note on da Costa-Doria ``exotic formalizations'' |
scientific article |
Statements
A note on da Costa-Doria ``exotic formalizations'' (English)
0 references
27 October 2010
0 references
The joint work of da Costa and Doria on consistency results for P versus~NP, via a so-called ``exotic definition'' for the problem [\textit{N. C. A. da Costa} and \textit{F. A. Doria}, Appl. Math. Comput. 145, No.~2--3, 655--665 (2003); addendum ibid. 172, No.~2, 1364--1367 (2006; Zbl 1046.68060)], has drawn criticism from various directions. The present paper's approach to debunking da Costa-Doria is to show that their results hold not just for P = NP, but for \textsl{every} sentence in the language of Peano arithmetic, thus making it ``doubtful that exotic formalizations alone could provide crucial insights into the nature of relative consistency of highly specific problems like P vs.~NP''.
0 references
first-order theories
0 references
Gödel's theorem
0 references
proof theory
0 references
P vs. NP
0 references
exotic formalizations
0 references