You are viewing a javascript disabled version of the site. Please enable Javascript for this site to function properly.
Go to headerGo to navigationGo to searchGo to contentsGo to footer
In content section. Select this link to jump to navigation

A Sufficient Condition for the Consistency of P=NP with Peano Arithmetic

Article type: Research Article

Authors: Kowalczyk, Wojciech

Affiliations: University of Warsaw

Abstract: In this paper we show how the indicators technique due to Paris and Kirby may be used to obtain independence or consistency results in Computer Science. We give an example of a sentence which is independent of PA and we formulate a sufficient condition for the consistency of P=NP with Peano Arithmetic.

Keywords: independence, consistency, nonstandard model of Peano Arithmetic, indicator, provably recursive function, P=NP problem

DOI: 10.3233/FI-1982-5207

Journal: Fundamenta Informaticae, vol. 5, no. 2, pp. 233-245, 1982

Received 9 March 1982
|
Published: 1 April 1982
Price: EUR 27.50
Show more