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

DOI10.1145/3209108.3209155zbMath1502.68127OpenAlexW2798907744MaRDI QIDQ5145296

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

Mathematics Subject Classification ID

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

Related Items (1)

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