Svårigheten att nå problemet med levande och säkra petrinät har varit öppen i flera år. Flera partiella resultat verkade tyda på att problemet är polynom. Vi visar att detta är osannolikt: problemet är NP-komplett. Fritt val Petri nät var rst de ned och studerades i början av sjuttiotalet 1, 7]. Idag är de accepterade som den största klassen av Petri nät för vilka relevanta analysproblem kan lösas i polynom tid. 1 En serie av papper, som börjar med 5] och kulminerar med 10] har visat att problemet med att avgöra om ett fritt val Petri nät är live och avgränsas kan lösas i O(n m) tid, där n och m är antalet platser och övergångar av nätet, respektive. I sin tur har många analys problem med levande och avgränsade frival Petri nät också visat sig ha polynom tid komplexitet 4]. På grund av denna resultatserie har man sedan omkring 1991 också ansett att det är polynomiskt att avgöra om en viss märkning kan nås från den ursprungliga märkningen, problemet med levande och avgränsade petrinät, dvs. problemet med att avgöra om en viss märkning kan nås från den ursprungliga märkningen. Trots vissa mycket lovande partiella resultat har dock ett bevis förblivit svårfångat. I 2] det visades att när Petri nätet är också cykliskt 2 då kan nåbarhetsproblemet reduceras till att lösa ett system av n vanliga linjära ekvationer med m variabler, och är därför polynom. Senare, 4] visade att varje nåbar märkning kan nås från den ursprungliga märkningen genom en händelse sekvens av längd O(b m 3 ), där b är gränsen för nätet, dvs. det maximala antalet polletter som en nåbar märkning kan sätta på en plats. Mer nyligen, 11] gav en strukturell karakterisering av uppsättningen av nåbara markeringar som verkade vara ett viktigt steg mot en polynomal algoritm, och 9] visade hur man bestämmer i O(n + m) 3 ) tid om två givna platser kan samtidigt markeras. Delvis stödd av Sonderforschungsbereich 342, Teilprojekt A3. 1 Även om vissa av resultaten gäller för frival av Petri nät har utökats till något större klasser. 2 Ett Petrinät är cykliskt om den ursprungliga märkningen kan nås från någon annan tillgänglig märkning.
Nåbarhetsproblemet för vissa specifika Petri-nät, såsom konfliktfria Petri-nät och 1 säkra levande frivalsnät REF, är NP-komplett.
Reachability in Live and Safe Free-Choice Petri Nets is NP-Complete
{'venue': 'Theor. Comput. Sci.', 'journal': None, 'mag_field_of_study': ['Computer Science', 'Mathematics']}