@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?