A note on da Costa-Doria ``exotic formalizations'' (Q711567)

From MaRDI portal





scientific article; zbMATH DE number 5806727
Language Label Description Also known as
default for all languages
No label defined
    English
    A note on da Costa-Doria ``exotic formalizations''
    scientific article; zbMATH DE number 5806727

      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