[logic-ml] JAIST Logic Seminar Series

[Hajime Ishihara]

皆様

スワンジー大学のArnold Beckmann先生の講演のお知らせです。
どうぞふるってご参加ください。

問合せ先：
石原　哉
北陸先端科学技術大学院大学 情報科学系
e-mail: ishihara at jaist.ac.jp
-----------------------------------------------

* 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.