On the metamathematics of the P vs. NP question

DOI10.1016/j.amc.2006.12.012zbMath1126.03048OpenAlexW2021377075MaRDI QIDQ2383632

E. Bir, Francisco Antonio Doria, Newton C. A. Da Costa

Publication date: 19 September 2007

Published in: Applied Mathematics and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.amc.2006.12.012

zbMATH Keywords

independenceconsistencyPeano arithmeticZermelo-Fraenkel set theory\(\text{P}=\text{NP}\)

Mathematics Subject Classification ID

Research exposition (monographs, survey articles) pertaining to mathematical logic and foundations (03-02) Research exposition (monographs, survey articles) pertaining to computer science (68-02) Consistency and independence results (03E35) First-order arithmetic and fragments (03F30) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (5)

On the metamathematics of the P vs. NP question ⋮ Informal versus formal mathematics ⋮ A note on da Costa-Doria ``exotic formalizations ⋮ Some thoughts on hypercomputation ⋮ How to build a hypercomputer

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• P, NP, Co-NP and weak systems of arithmetic
• Undecidability and incompleteness in classical mechanics
• Logical number theory I. An introduction
• Consequences of an exotic definition for \(\text{P}=\text{NP}\).
• A Ramsey theorem in Boyer-Moore logic
• On the metamathematics of the P vs. NP question
• General recursive functions of natural numbers
• Nondeterministic polynomial-time computations and models of arithmetic
• The Expressiveness of Simple and Second-Order Type Structures
• Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question
• Hilbert's Tenth Problem is Unsolvable
• Transfinite Progressions: A Second Look at Completeness
• Transfinite recursive progressions of axiomatic theories
• On the Interpretation of Non-Finitist Proofs--Part I
• On the concepts of completeness and interpretation of formal systems

This page was built for publication: On the metamathematics of the P vs. NP question