A parameterized halting problem, ${\Delta }_0$ truth and the MRDP theorem

Yijia Chen, Moritz Müller, Keita Yokoyama

We study the parameterized complexity of the problem to decide whether a given natural number $n$ satisfies a given ${\Delta }_0$-formula $\phi (x)$; the parameter is the size of $\phi$. This par…