A parameterized halting problem, the linear time hierarchy, and the MRDP theorem

DOI10.1145/3209108.3209155zbMATH Open1502.68127OpenAlexW2798907744MaRDI QIDQ5145296FDOQ5145296

Keita Yokoyama, Moritz Müller, Yijia Chen

Publication date: 20 January 2021

Published in: Proceedings of the 33rd Annual ACM/IEEE Symposium on Logic in Computer Science (Search for Journal in Brave)

Full work available at URL: http://hdl.handle.net/2117/119165

Recommendations

• A Parameterized Halting Problem
• A logic for PTIME and a parameterized halting problem
• Computation Models for Parameterized Complexity
• On the bounded version of Hilbert's tenth problem
• Machine characterizations for parameterized complexity classes beyond para-NP

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) First-order arithmetic and fragments (03F30) Complexity of computation (including implicit computational complexity) (03D15) Turing machines and related notions (03D10) Parameterized complexity, tractability and kernelization (68Q27)

Cited In (2)

• A Parameterized Halting Problem
• Some lower bounds in parameterized \(\mathrm{AC}^{0}\)

This page was built for publication: A parameterized halting problem, the linear time hierarchy, and the MRDP theorem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5145296)