逸仙逻辑讲坛第二十六期｜陈翌佳：A halting problem and the MRDP Theorem

A halting problem, model-checking of ∆0-formulas, and the MRDP Theorem

发布日期：2025-01-04
主题
A halting problem, model-checking of ∆0-formulas, and the MRDP Theorem
活动时间
-
活动地址
锡昌堂322室
主讲人
陈翌佳 
主持人
王   玮
image-20250108112112-1

第二十六期  逸仙逻辑讲坛

题目：A halting problem, model-checking of ∆0-formulas, and the MRDP Theorem

主讲人：陈翌佳  上海交通大学

            计算机科学与工程系

主持人：王   玮  中山大学

            哲学系暨逻辑与认知研究所

时   间：1月6日（周一）下午15:00

地   点：中山大学锡昌堂322室

主办方：中山大学逻辑与认知研究所

 

主讲人简介 

       陈翌佳是上海交通大学计算机科学教授。他在上海交通大学获得计算机科学博士学位，在弗赖堡大学获得数学博士学位。他主要从事计算机科学中的逻辑、计算复杂性和算法图论的工作。他在 Logic Methods in Computer Science 和 Theory of Computing Systems 的编委会任职。

 

内容简介 

Consider the following two problems:

  1. Given a nondeterministic Turing machine  and a natural number , decide whether M halts on the empty tape in at most n steps.
  2. Given a  formula  (i.e., every quantifier in  is bounded) and a natural number , decide whether . Their classical complexities are well known and very different. However, we are still far from pinpointing the parameterized complexity of these two problems, which turn out to be intimately connected. In this talk, I will demonstrate that settling their parameterized complexity will have remarkable consequences in classical complexity theory. Perhaps surprisingly, the provability of the celebrated MRDP theorem in bounded arithmetic plays an important role in our investigation.

This is joint work with Moritz Müller (Passau) and Keita Yokoyama (Tohoku).