@John

> The situation for Petri net reachability is much less well understood. In 1976, [Roger Lipton showed that its complexity is at least exponential](http://www.cs.yale.edu/publications/techreports/tr63.pdf). More precisely, he showed the for any \$$c > 0\$$ the worst-case run-time for deciding Petri net reachability exceeds \$$2^{cn}\$$ where \$$n\$$ is the size of the problem.

It's worse than that - the proof regards *space*, not *time*. That paper establishes you need at least \$$\mathcal{O}(2^{n})\$$ memory to solve the reachability problem. Since you can't writing to all that memory demands the algorithm take the time to do it, it *also* entails the algorithm is in \$$\textsf{EXP-TIME}\$$.

@Tobias

The same Roger Lipton cited above cowrote another paper in 1976 establishing that any \$$\textsf{EXP-SPACE}\$$ algorithm can be expressed as a Petri net reachability problem.

I used this to argue \$$\textsf{NP} \subsetneq \textsf{PETRI-REACH}\$$ in [comment #41](https://forum.azimuthproject.org/discussion/comment/17886/#Comment_17886) in this thread. I had a few false starts with this - do you think this argument is adequate?