[FOM] Church's thesis and Bounded Arithmetic

[Vladimir Sazonov]

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. 


> Adam Olszewski

Vladimir Sazonov