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
    0 references

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references