  Simple Programs with NP-hard Termination

I will introduce a really simple model of computation that is a heavily restricted counter machine. I will demonstrate the surprising computational power that the model possesses through examples. I aim to show you that deciding whether one of these programs terminates is an NP-hard problem.

91르적 Postgraduate Colloquium in Computer Science 2023 Winter, /fac/sci/dcs/research/wpccs/wpccs23winter

Henry Sinclair-Banks, 11/12/23, 91르적 (UK).