TY - JOUR A1 - Chen, Yijia A1 - Müller, Moritz A1 - Yokoyama, Keita T1 - A parameterized halting problem, Δ0 truth and the MRDP theorem JF - The Journal of Symbolic Logic (ISSN 1943-5886) N2 - 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 AC0. 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. KW - bounded arithmetical truth KW - parameterized halting KW - descriptive complexity KW - weak arithmetic KW - MRDP theorem Y1 - 2024 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:bvb:739-opus4-19308 SN - 1943-5886 VL - 90 (2025) IS - 2 SP - 483 EP - 508 PB - Cambridge University Press CY - Cambridge ER -