三划分问题可多项式归约为唯一可达向量Petri网可达性问题

Three Partition Problem is Polynomial Time Reducible to the Reachability Problem of the URV-PNs

为了对基于唯一可达向量Petri网(URV-PN)的密码体制进行密码分析工作,有必要对唯一可达向量网系统的数学本质和各种性质进行深入的研究.定义了扩展的三划分问题,三划分问题是扩展的三划分问题的一种特殊情况;给出了一个一般的多项式时间复杂度算法构造扩展的三划分问题的Petri网模型;证明扩展的三划分问题有解当且仅当所构造的Petri网模型中某个标识可达;从而说明三划分问题可多项式归约为唯一可达向量Petri网系统的可达性问题,从而给出了求解唯一可达向量网系统可达性问题的一个复杂度下界.

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 （URVPN） 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 teachability problem of the URV-PN is proved to be NP-hard.