An Easy-Sounding Problem Yields Numbers Too Big for Our Universe
For the past 50 years, Vector Addition Systems—a simple but powerful computational model—have been a topic of great interest in theoretical CS. The reachability problem in that model asks whether we can get from some configuration to another.
The problem sounds relatively easy on a first glance, and an exponential lower bound held firm for over 40 years. Work by excellent theoreticians, including familiar names from Warwick DCS, finally closed the difficulty of the problem in 2021, concluding that it is very, very difficult indeed.