Is there a simple, pedestrian arithmetic sentence which is independent of ZFC?

Francisco A. Doria

pp. 69-76

in: Synthese 125, 2000.

Abstract

We show that the P < NP conjecture can beformulated as a Pi20 sentence, and explore some of theconsequences of that fact. This paper summarizes recent workby the author with N. C. A. da Costa on the P