期刊名称：The Baltic International Yearbook of Cognition, Logic and Communication
印刷版ISSN：1944-3676
出版年度：2013
卷号：8
出版社：New Prairie Press
摘要：The present article introduces ptarithmetic (shortfor "polynomial time arithmetic") ¡ª a formal number theory sim-ilar to the well known Peano arithmetic, but based on the recentlyborn computability logic instead of classical logic. The formulas ofptarithmetic represent interactive computational problems ratherthan just true/false statements, and their "truth" is understood asexistence of a polynomial time solution. The system of ptarith-metic elaborated in this article is shown to be sound and com-plete. Sound in the sense that every theorem T of the system rep-resents an interactive number-theoretic computational problemwith a polynomial time solution and, furthermore, such a solu-tion can be effectively extracted from a proof of T . And completein the sense that every interactive number-theoretic problem witha polynomial time solution is represented by some theorem T ofthe system
