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

DOI10.1145/3209108.3209155MaRDI QIDQ5145296zbMATH OpenOpenAlexFDO

Authors Yijia Chen, Moritz Müller, Keita Yokoyama

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 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)

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

Cited in

(3)

• A Parameterized Halting Problem
• Some lower bounds in parameterized \(\mathrm{AC}^{0}\)
• A logic for PTIME and a parameterized halting problem

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)