皆様
スワンジー大学のArnold Beckmann先生の講演のお知らせです。 どうぞふるってご参加ください。
問合せ先： 石原 哉 北陸先端科学技術大学院大学 情報科学系 e-mail: [email protected] -----------------------------------------------
* JAIST Logic Seminar Series *
* The seminar below is held as a part of JSPS Core-to-Core Program, A. Advanced Research Networks, EU FP7 Marie Curie Actions IRSES project CORCON. (http://www.jaist.ac.jp/logic/ja/core2core, https://corcon.net/), and EU Horizon 2020 Marie Skłodowska-Curie actions RISE project CID.
Date: Friday 15, September, 2017, 15:20-17:00
Place: JAIST, Collaboration room 7 (I-56) (Access: http://www.jaist.ac.jp/english/location/access.html)
Speaker: Professor Arnold Beckmann (University of Swansea, Head of Department of Computer Science) http://www.cs.swan.ac.uk/~csarnold/
Title: Provably Total NP Search Problems of Bounded Arithmetic and beyond
Abstract: Bounded Arithmetic forms a collection of weak theories of Arithmetic related to complexity classes of functions like the Polynomial Time Hierarchy. Many connections between Bounded Arithmetic and important questions about complexity classes have already been established. Recent research considers total NP search problems in the context of Bounded Arithmetic. Total NP search problems have been studied by Papadimitriou et al as a means to characterise the complexity of natural search problems which cannot be analysed as decision problems.
In my talk I will review the research programme of characterising the provably total NP search problems in Bounded Arithmetic, and explain why it is important for current research questions in the area. I will describe recent results about the provably total NP search problems of a Bounded Arithmetic theories related to PSPACE and EXPTIME reasoning. I will also describe this program for theories beyond Bounded Arithmetic like Peano arithmetic, and what impact this might have on Complexity Theory.