...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Algorithmica >Polynomial Kernels and User Reductions for the Workflow Satisfiability Problem
【24h】

Polynomial Kernels and User Reductions for the Workflow Satisfiability Problem

机译：工作流可满足性问题的多项式核和用户约简

获取原文
获取原文并翻译 | 示例
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

The workflow satisfiability problem (wsp) is a problem of practical interest that arises whenever tasks need to be performed by authorized users, subject to constraints defined by business rules. We are required to decide whether there exists a plan-an assignment of tasks to authorized users-such that all constraints are satisfied. The wsp is, in fact, the conservative constraint satisfaction problem (i.e., for each variable, here called task, we have a unary authorization constraint) and is, thus, -complete. It was observed by Wang and Li (ACM Trans Inf Syst Secur 13(4):40, 2010) that the number of tasks is often quite small and so can be used as a parameter, and several subsequent works have studied the parameterized complexity of wsp regarding parameter . We take a more detailed look at the kernelization complexity of wsp( ) when denotes a finite or infinite set of allowed constraints. Our main result is a dichotomy for the case that all constraints in are regular: (1) We are able to reduce the number of users to . This entails a kernelization to size poly for finite , and, under mild technical conditions, to size poly for infinite , where denotes the number of constraints. (2) Already wsp( ) for some allows no polynomial kernelization in unless the polynomial hierarchy collapses.
机译：工作流可满足性问题（wsp）是实际需要解决的问题，每当需要授权用户执行任务时，都会受到业务规则定义的约束的影响。我们需要决定是否存在计划-将任务分配给授权用户-以便满足所有约束条件。实际上，wsp是保守约束满足问题（即，对于每个变量，在这里称为任务，我们具有一元授权约束），因此，-sp是完整的。 Wang和Li（ACM Trans Inf Syst Secur 13（4）：40，2010）观察到，任务数量通常很小，因此可以用作参数，随后的几项工作研究了参数化的复杂度。关于参数的wsp。当wsp（）表示允许的约束的有限或无限集合时，我们将更详细地研究wsp（）的内核化复杂度。对于所有约束都是规则的情况，我们的主要结果是二分法：（1）我们能够将用户数量减少到。这就需要对poly的大小进行有限化，在温和的技术条件下，对poly的大小进行无限化，其中表示约束的数量。 （2）除非多项式层次结构崩溃，否则对于某些人而言，wsp（）已经不允许进行多项式内核化。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号