The complexity of the reachability problem for live and safe free-choice Petri nets has been open for several years. Several partial results seemed to indicate that the problem is polynomial. We show that this is unlikely: the problem is NP-complete. Free-choice Petri nets were rst de ned and studied in the early seventies 1, 7]. Today, they are accepted as the largest class of Petri nets for which relevant analysis problems can be solved in polynomial time. 1 A series of papers, starting with 5] and culminating with 10], has shown that the problem of deciding if a free-choice Petri net is live and bounded can be solved in O(n m) time, where n and m are the number of places and transitions of the net, respectively. In turn, many analysis problems of live and bounded free-choice Petri nets have also been shown to have polynomial time complexity 4]. Due to this series of results, the reachability problem of live and bounded free-choice Petri nets, i.e., the problem of deciding if a given marking is reachable from the initial marking, has also been believed to be polynomial since around 1991. However, despite some very promising partial results, a proof has remained elusive. In 2] it was shown that when the Petri net is also cyclic 2 then the reachability problem can be reduced to solving a system of n ordinary linear equations with m variables, and is therefore polynomial. Later, 4] proved that every reachable marking can be reached from the initial marking by an occurrence sequence of length O(b m 3 ), where b is the bound of the net, i.e., the maximum number of tokens that a reachable marking can put in a place. More recently, 11] provided a structural characterization of the set of reachable markings which seemed to be an important step towards a polynomial algorithm, and 9] showed how to decide in O((n + m) 3 ) time whether two given places can be simultaneously marked. Partially supported by the Sonderforschungsbereich 342, Teilprojekt A3. 1 Although some of the results valid for free-choice Petri nets have been extended to slightly larger classes. 2 A Petri net is cyclic if the initial marking is reachable from any other reachable marking.
The reachability problem for some specific Petri nets, such as conflict-free Petri nets and 1 safe live free-choice nets REF , is NP-complete.
Reachability in Live and Safe Free-Choice Petri Nets is NP-Complete
Theor. Comput. Sci.
Computer Science Mathematics