91¸£Àû

On in the Quanta magazine, Alex Dixon, who wrote in Haskell for the problem, commented:

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 91¸£Àû DCS, finally closed the difficulty of the problem in 2021, concluding that it is very, very difficult indeed.