Speaker
Description
A Petri net is a mathematical modeling language, which is used mainly for verification of concurrent programs, but it also can model processes in economy or even in biology and chemistry. One of the advantages is the simplicity: a Petri net consists of a set of places on which we can put tokens, and a set of transitions i.e. rules according to which we can add and remove tokens from places. The reachability problem is to decide whether for a given Petri net and two configurations one is reachable from the another. This problem was shown to be decidable (i.e. there is an algorithm that solves it) over 40 years ago, but until 2021 the exact computational complexity was not known! The reachability problem is Ackermann-complete, which means that its complexity is so huge, that it cannot be bounded by any elementary function. In my talk I will explain what is a Petri net using examples and mini tasks that I hope will be fun. Then I will define the Ackermann complexity class, convince you that it is really big, and at the end I will talk shortly about the history and open questions.
| Field | Computer science |
|---|---|
| Length | Short 15 min |
