Three Partition Problem is Polynomial Time Reducible to the Reachability Problem of the URV-PNs
Yue Hao · Microelectronics & Computer · 2008
The extended three partition problem which is the general case of the three partition problem is proposed in this paper. The goal is to discover the mathematical nature and property of the Unique Reachability Vector Petri Net (URV-PN) for the cryptanalysis of the cryptography system based on the URV-PN. Therefore, a polynomial time algorithm for reducing the extended three partition problem to the reachability problem of the URV-PN is developed. So the reachability problem of the URV-PN is proved to be NP-hard.