みなさま
今週木曜日に京都大学にてThomas Seillerさんによるご講演があります。 詳細は下記の通りです。よろしければぜひご参加ください。
京都大学数理解析研究所 照井一成
========== Time: 11:00-12:00, October 3rd, 2019 Place: Rm 478, Research Building 2, Main Campus, Kyoto University 京都大学 本部構内 総合研究2号館 4階478号室 http://www.kyoto-u.ac.jp/en/access/yoshida/main.html (Building 34)
Speaker: Thomas Seiller (LIPN, University of Paris 13)
Title: Dynamical systems and computational complexity
Abstract: Based on previous work on semantics of linear logic which used the notion of “graphing”, I started to study how these mathematical objects, which generalize partial dynamical systems, can shed new light on computability.
Focussing on questions of complexity, Pellissier and I recently showed how interpreting programs as dynamical systems can lead to an abstract method for proving lower bounds that capture several previously known results. More importantly, the method can be refined to strengthen the previously best-known partial result towards settling the Ptime vs NC question negatively.
Building on some realisability construction for linear logic capturing standard complexity classes, this leads to wonder about how much can be learned from dynamical systems, and if the field can provide new insights on important questions such that “Is Ptime equal to Logspace?”.