工作流可满足性(≠,=)计数及其#P完全性  

Counting Workflow Satisfiability(≠,= ) and Its #P Completeness

作　　者：翟治年[1] 卢亚辉[2] 余法红[3] 周武杰[1] 向坚[1] 吴茗蔚[1] 

机构地区：[1]浙江科技学院信息与电子工程学院,浙江杭州310023 [2]深圳大学计算机学院,广东深圳518060 [3]嘉兴学院数理与信息学院,浙江嘉兴314001

出　　处：《电子学报》2017年第3期605-611,共7页Acta Electronica Sinica

基　　金：国家自然科学基金(No.61502429;No.61302112);浙江省自然科学基金(No.LQ15F020010;No.LY16F020027);浙江省教育厅科研项目(No.Y201533771);钱江人才计划(No.QJD1402023)

摘　　要：工作流可满足性(WS)是资源分配对访问控制(AC)策略提出的基本要求.相关工作主要围绕WS决策问题展开,通过找到一个具体的解来说明AC策略的正确性.然而为了进一步验证AC策略在资源异常情况下的合理性,统计所有解的数量将更有帮助.本文对互斥和绑定约束下的WS计数问题进行研究,通过构造从典范性#P完全问题#3SAT到该问题的多项式计数归约,证明其属于#P完全问题,为其恰当地求解奠定了理论基础.Workflow satisfiability （WS） is an essential claim to access control （AC） policies from the view of resource allocation. So far,the related researches are concentrated on the decision problem of WS, which finds a single solution to show the correctness of an AC policy. However, to further verify its rationality under resource exception, and to count all the solutions will be more useful. In this paper, the counting problem of WS with exclusion and binding constraints is addressed. The problem is proved to be #P complete by constructing a polynomial time counting reduction from the well-known #P complete problem of #3 SAT to it, and then gets a theoretical basis to be solved appropriately.

关 键 词：工作流 访问控制 授权 约束 资源分配 可满足性 

分 类 号：TP309[自动化与计算机技术—计算机系统结构]