Editing EXPSPACE (section)

=== Petri nets ===
The coverability problem for [[Petri Nets]] is {{Sans-serif|EXPSPACE}}-complete.<ref>{{cite journal | 
  author = Charles Rackoff |
  title = The covering and boundedness problems for vector addition systems |
  journal = Theoretical Computer Science |
  pages = 223–231 |
  date = 1978}}</ref>

The [[reachability problem]] for Petri nets was known to be {{Sans-serif|EXPSPACE}}-hard for a long time,<ref>{{cite journal | last = Lipton | first = R. | url = http://citeseer.ist.psu.edu/contextsummary/115623/0 | title = The Reachability Problem Requires Exponential Space | journal = Technical Report 62 | publisher = Yale University | date = 1976 }}</ref> but shown to be [[Nonelementary problem|nonelementary]],<ref>{{cite conference | author = Wojciech Czerwiński Sławomir Lasota Ranko S Lazić Jérôme Leroux Filip Mazowiecki
| title = The reachability problem for Petri nets is not elementary | book-title = STOC 19 | date = 2019}}</ref> so probably not in {{Sans-serif|EXPSPACE}}. In 2022 it was shown to be [[Ackermann function|Ackermann]]-complete.<ref name=":1">{{Cite book |last=Leroux |first=Jerome |chapter=The Reachability Problem for Petri Nets is Not Primitive Recursive |date=February 2022 |title=2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS) |chapter-url=https://ieeexplore.ieee.org/document/9719763 |publisher=IEEE |pages=1241–1252 |doi=10.1109/FOCS52979.2021.00121 |isbn=978-1-6654-2055-6|arxiv=2104.12695 }}</ref><ref name=":0">{{Cite web |last=Brubaker |first=Ben |date=4 December 2023 |title=An Easy-Sounding Problem Yields Numbers Too Big for Our Universe |url=https://www.quantamagazine.org/an-easy-sounding-problem-yields-numbers-too-big-for-our-universe-20231204/ |website=[[Quanta Magazine]]}}</ref>