# [FOM] Church's thesis and Bounded Arithmetic

Vladimir Sazonov V.Sazonov at csc.liv.ac.uk
Wed Jun 25 07:04:10 EDT 2003

addamo at wp.pl wrote:
>
> Dear Professor Sazonov,
>
> I am interested in Church's Thesis. You have written about some connections
> between CT and the Bounded Arithmetic.
> Could you give me some references on this theme?

I have two versions of a paper on that

Shorter one:

An equivalence between polynomial constructivity of
Markov's principle and the equality P=NP, in:  P.Petkov, ed.,
Mathematical Logic, Proceedings of the Summer  School and Conference on
Mathematical Logic dedicated to the Ninetieth Anniversary of Arend
Heyting, 1988, Varna, Bulgaria. 1990, Plenum Press, New York, pp.
351--360.

This is probably available in libraries.

A longer one, translated in English from Russian:

An equivalence between polynomial constructivity of
Markov's principle and the equality P=NP,
{\em Siberian Advances in Mathematics\/}, 1991, v.1, N4, pp. 92-121
(English translation of a paper in Russian published in
Matematicheskaja logika i algoritmicheskie problemy, Trudy Instituta
matematiki SO AN SSSR, 12, Novosibirsk, Nauka'', Sibirskoe
otdelenie, 1989, pp. 138--165.)

I hope this is also available. However, I could send you
a copy by post.

Actually, these papers are about a version of so called Russian
Constructivism relativised to a version of BA (instead of Heyting
Arithmetic HA). The main result may be formulated as follows:

An intuitionistic version of BA + ECT + M is constructive
iff P=NP.

ECT is Extended Church Thesis (which contradicts to BA formulated
in classical logic)

M is Markov's Principle.

"Constructive" is understood in a relative way.

Also, provably (total) recursive function of the above theory
are exactly those computable in PTIME.

If BA above is replaced by HA then the resulting theory is known
to be constructive.

Let me mention also some related and independent approaches by
Buss, and Cook and Urquhart.