🚀 go-pugleaf

Lecture Series ``Collegium Logicum''
Kurt Goedel Society
University of Technology, Vienna, Austria


Lecture Announcement
--------------------

Vladimir Yu. Sazonov
====================
Russian Academy of Sciences, Pereslavl-Zalessky

An Equivalence Between Polynomial Constructivity of 
Markov's Principle and the Equality P=NP		
-------------------------------------------------------------
Monday, April 3, 1995, 16:45


ABSTRACT:
 
Call any theory C constructive if for any Harrop's
formula H and arbitrary F

        C |- H(x)  --> exists y F(x,y)

         implies

        C |-  H(x) --> F(x,{t}(x))

for some signature term t in C containing  no  variables.  

There are two main results:

I.  The principles  ECT  (Extended  Church  Thesis)  and   M   (Markov's
Principle)  are  constructive   relative   to   HPT   (Heyting,   or
Intuitionistic Theory of Polytime Computability) iff P=NP holds.

II. Superpolynomial complexity of NP-complete problems acceptability
is not provable in HPT + ECT + M.

Provably-recursive functions of the latter theory are just Polytime
computable ones. Note, that this property of a theory  does not 
guarantee that in general a result of type II will hold for it. 
Also, the notion of constructive finite binary string plays an
important role here. In contrast to strong theories like PA or 
PRA where exponentiation is a provably total function, 
it is unprovable in PT that each string is constructive.

PLACE:

Seminarraum SEM 181A, Institut fuer Informationssysteme,
Paniglgasse 16, 1. Stock, 1040 Wien.

------------------------
Kurt-Goedel-Gesellschaft
Technische Universitaet Wien
Institut fuer Computersprachen E185.2
Resselgasse 3/1, A-1040 Wien

Tel: (+43 1) 588 01/4088
Fax: (+43 1) 504 15 89
email: kgs@logic.tuwien.ac.at
http://logic.tuwien.ac.at:80/kgs/home.html 

Mit Unterstuetzung des
Bundesministeriums fuer Wissenschaft und Forschung