论文标题
一个参数化的停止问题，$Δ_0$真相和MRDP定理
A parameterized halting problem, $Δ_0$ truth and the MRDP theorem
论文作者
论文摘要
我们研究了问题的参数化复杂性，以决定给定的自然数量$ n $是否满足给定的$Δ_0$ -formula $φ（x）$；参数的大小为$φ$。与$φ$相比，这种参数化将注意力集中在$ n $大的实例上。我们无条件地表明，此问题不属于$ \ mathsf {ac}^0 $的参数化类似物。由此，我们得出了某些自然上限，即我们的参数化问题的复杂性意味着经典复杂性类别的某些分离。通过对参数化停止问题的分析获得此连接。假设$iΔ_0$在某种弱的意义上证明了MRDP定理，则其中一些上限。
We study the parameterized complexity of the problem to decide whether a given natural number $n$ satisfies a given $Δ_0$-formula $φ(x)$; the parameter is the size of $φ$. This parameterization focusses attention on instances where $n$ is large compared to the size of $φ$. We show unconditionally that this problem does not belong to the parameterized analogue of $\mathsf{AC}^0$. From this we derive that certain natural upper bounds on the complexity of our parameterized problem imply certain separations of classical complexity classes. This connection is obtained via an analysis of a parameterized halting problem. Some of these upper bounds follow assuming that $IΔ_0$ proves the MRDP theorem in a certain weak sense.
