[ont.events] Peter Clote: "Model techniques in complexity theory"

phyllis@utcsrgv.UUCP (Phyllis Eve Bregman) (03/16/84)

      UofT Department of Computer Science Seminar Schedule for
                the week of March 19th, 1984
		
Wednesday, March 21th, 4:00 P.M., SF3202:  Professor Peter Clote,
   Department of Computer Science, University of Toronto (Visiting
   from University Paris VII):  "Model techniques in complexity
   theory".

   ABSTRACT:  This talk surveys some applications of techniques in
   "models of arithmetic" to complexity theory:  a model theoretic
   equivalence of P = NP and of the collapse of the Stockmeyer hierarchy
   (Paris-Dimitricopoulos), model theoretic criteria for whether a
   set is rudimentary or strictly rudimentary (Paris-Wilkie), a
   brief look at the theory PT of Lipton-DeMillo, and on computing
   upper bounds for problems associated with Petri nets (McAloon and
   Clote).
-- 
		Phyllis Eve Bregman
		CSRG, Univ. of Toronto
		{decvax,linus,ihnp4,uw-beaver,allegra,utzoo}!utcsrgv!phyllis
		CSNET:  phyllis@toronto
		(416) 978 6985