Reference:

J. Esparza. Reachability in live and safe free-choice Petri nets is -complete. Theoretical Computer Science, 198(1–2):211–224, 1998.

Abstract:

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 -complete.

Suggested BibTeX entry:

@article{Esp98b,
    author = {J. Esparza},
    journal = {Theoretical Computer Science},
    number = {1--2},
    pages = {211--224},
    title = {Reachability in Live and Safe Free-choice {P}etri Nets is {$NP$}-complete},
    volume = {198},
    year = {1998}
}