Jonathan Castello - [nice comment](https://forum.azimuthproject.org/discussion/comment/17830/#Comment_17830)! Everything you said sounds right to me.

> It isn't obvious whether Petri net reachability is in NP at all.

I'm no good at computational complexity, so I could be missing something obvious, but hope that if this problem were known to be in NP I'd have bumped into this fact during my literature search.

In 1976, Roger J. Lipton showed that any algorithm for solving the Petri net reachability problem requires least an exponential amount of memory space:

* Roger J. Lipton, The reachability problem requires exponential space, Technical Report 62, Yale University, 1976.

and thus also at least an exponential amount of time. As far as I know, this doesn't rule out the possibility that this problem is in \$$\text{NP}\$$. But maybe I'm missing some theorems.