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

• 作者: 岳昊
• 来源期刊: 微电子学与计算机
• 关键词: Petri网 三划分问题 归约 可达性问题 NP-难
• 年，卷（期）: 2008,（10）
• 页码范围: 144-146
• 页数: 3页
• 分类号: TP301
• 语种: 中文

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	岳昊	山东科技大学信息学院	9	57	5.0	7.0