Chen, Yijia
Title: A parameterized halting problem, the linear time hierarchy, and the MRDP theorem
Abstract: The complexity of the parameterized halting problem for nondeterministic Turing machines p-Halt is known to be related to the question of whether there are logics capturing various complexity classes. Among others, if p-Halt is in para-AC^0, the parameterized version of the circuit complexity class AC^0, then AC^0 has a logic. Although it is widely believed p-Halt\notin para-AC^0, we show that the problem is hard to settle by establishing a connection to a question in classical complexity of whether NE\notsubseteq LINH. Here, LINH denotes the linear time hierarchy. On the other hand, we suggest an approach toward proving NE\notsubseteq LINH using bounded arithmetic. More specifically, we demonstrate that if the much celebrated MRDP (for Matiyasevich-Robinson-Davis-Putnam) theorem can be shown in a certain fragment of arithmetic, then NE\notsubseteq LINH. Interestingly, another parameterized problem plays an important role in the proof of this result.
This is joint work with Moritz Mueller (Vienna), Jan Pich (Vienna), and Keita Yokoyama (JAIST).