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.

Warwick Postgraduate Colloquium in Computer Science 2023 Winter, https://warwick.ac.uk/fac/sci/dcs/research/wpccs/wpccs23winter

Henry Sinclair-Banks, 11/12/23, University of Warwick (UK).