On the Consistency of P=NP with Peano Arithmetic

Newton C. A. da Costa & Francisco Antonio Doria

We formulate the P < NP hypothesis for the satisfiability problem as a Pi-zero-two sentence out of which we can construct a partial recursive function f so that f is total if and only if P < NP. We then show that if f is total then it isn’t PA-provably total. Follows that P = NP is consistent with PA. We then discuss the extension of that result to fragments of ZFC whose consistency is of ordinal order.

Addresses Newton C. A. da Costa: Grupo de Lógica e Fundamentos/Logic & Foundations Group, Instituto de Estudos Avançados/Institute for Advanced Studies, Universidade de São Paulo, São Paulo, SP 05655-010 Brasil/Brazil.

E-mail: ncacosta@usp.br

Francisco Antonio Doria: Grupo de Lógica e Fundamentos/Logic & Foundations Group, Instituto de Estudos Avançados/Institute for Advanced Studies, Universidade de São Paulo, São Paulo, SP 05655-010 Brasil/Brazil.

E-mail: fadoria@rio.com.br