The reachability problem for Petri nets is not elementary.

Wojciech Czerwinski, Slawomir Lasota, Ranko Lazic, Jrme Leroux, Filip Mazowiecki

Browse the full STOC paper archive.