Unrelated but the coolest thing I discovered while researching this piece was that Petri Net reachability is decidable but Ackermann-complete. ACK-COMPLETE is a thing. That's wild.
what does that mean exactly? I skimmed the paper you linked briefly, but couldn't quite tell.
Does it mean that deciding reachability of an N-state petri net takes Ack(N) steps in the worst case? Or that you can can construct a Petri net which has a node reachable after Ack(N) steps?
Those are different I think since you can compute Ack(N) in fewer than Ack(N) steps.
I also wonder if you can more efficiently rule out polynomial-time reachability of a Petri net node, even if it is eventually reachable.
The former, though it grows a little slower than Ack(N). If I read the paper write, they showed that an 18-state Petri Net has a worst case reachability problem on the order of Ack(3), and then every six states you add, n goes up by one. So a 24 state Petri net can take Ack(4) steps to decide, for a 30 state Petri net Ack(5), etc. This is just the decision problem, not the length of the path.
(The paper is actually works on *Vector Addition Systems*, but VASes are isomorphic to Petri nets.)
Note these are loose boundaries: adding at most six states will definitely bump the hardness by at least 1, but it might grow faster than that. At the end of the paper they note some people have gotten more precise boundaries, that 10-states is "Tower-hard" (Ack(3)), and every 2 states bumps it by 1. So worst case for a 12-state net is on the order of Ack(4), etc.
