کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4635508 | 1340712 | 2007 | 18 صفحه PDF | دانلود رایگان |
We review the work (from 1976 to 1996) by several researchers on the metamathematics of P vs. NP. That work points towards the possibility that, given some strong consistent axiomatic system S with a recursively enumerable set of theorems which includes arithmetic, for the Σ2 sentence [P=NP][P=NP] that formalizes the P=NPP=NP hypothesis, S+[P=NP]S+[P=NP] is consistent. We consider the work of several authors like for instance [J. Hartmanis, J. Hopcroft, Independence results in computer science, SIGACT News 13 (1976); M. O’Donnell, A programming language theorem which is independent of Peano Arithmetic, in: Proceedings of the 11th Annual ACM Symposium on the Theory of Computation, 1979, pp. 176–188; R.A. DeMillo, R.J. Lipton, The consistency of P = NP and related problems with fragments of number theory, in: Proceedings of the 12th Annual ACM Symposium on the Theory of Computing, 1980, pp. 45–57; D. Joseph, P. Young, Fast programs for initial segments and polynomial time computation in weak models of arithmetic, STOC Milwaukee 1981, 1981, pp. 55–61; W. Kowalczyk, A sufficient condition for the consistency of P = NP with Peano Arithmetic, Fund. Inform. 5 (1982) 233–245]. We then relate all those results to the [N.C.A. da Costa, F.A. Doria, Consequences of an exotic formulation for P = NP , Appl. Math. Comput. 145 (2003) 655–665, also “Addendum” 172 (2006) 1364–1367] conditional consistency result for ZFC+[P=NP]ZFC+[P=NP] and elaborate on it.
Journal: Applied Mathematics and Computation - Volume 189, Issue 2, 15 June 2007, Pages 1223–1240