slideshow 3

Logic seminar

On the parameterized complexity of Delta-0 truth

Moritz Müller
University of Passau


Monday, 21. November 2022 - 16:00 to 17:30
Online - - contact before the meeting to join
We consider the problem, given a Δ0 formula φ(x) and a natural number n in unary, whether φ(n) is true. We are interested in instances of the problem where n is much bigger than φ. More precisely, we consider the parameterized problem with parameter |φ|. We show unconditionally that this problem does not belong to the parameterized version of AC0. We also show that certain natural upper bounds on the parameterized complexity of the problem imply separations of classical complexity classes. These results are obtained by an analysis of a parameterized halting problem. A related problem concerns the provability of the MRDP theorem in bounded arithmetic.