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

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

具有准备时间和延迟时间的自由作业问题的复杂性

讨论具有准备时间和延迟时间的自由作业问题 。