• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>International conference on principles and practice of constraint programming >Quantified Valued Constraint Satisfaction Problem
【24h】

Quantified Valued Constraint Satisfaction Problem

机译：量化值约束满足问题

获取原文
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

We study the complexity of the quantified and valued extension of the constraint satisfaction problem (QVCSP) for certain classes of languages. This problem is also known as the weighted constraint satisfaction problem with min-max quantifiers [1]. The multimorphisms that preserve a language is the starting point of our analysis. We establish some situations where a QVCSP is solvable in polynomial time by formulating new algorithms or by extending the usage of collapsibility, a property well known for reducing the complexity of the quantified CSP (QCSP) from Pspace to NP. In contrast, we identify some classes of problems for which the VCSP is tractable but the QVCSP is Pspace-hard. As a main Corollary, we derive an analogue of Shaeffer's dichotomy between P and Pspace for QCSP on Boolean languages and Cohen et al. dichotomy between P and NP-complete for VCSP on Boolean valued languages: we prove that the QVCSP follows a dichotomy between P and Pspace-complete. Finally, we exhibit examples of NP-complete QVCSP for domains of size 3 and more, which suggest at best a trichotomy between P, NP-complete and Pspace-complete for the QVCSP.
机译：我们研究了某些类语言的约束满足问题（QVCSP）的量化和值扩展的复杂性。这个问题也被称为带有最小-最大量词的加权约束满足问题[1]。保留语言的多态性是我们分析的起点。我们通过制定新算法或扩展可折叠性的使用，建立了在多项式时间内可解决QVCSP的情况，这是一种众所周知的可降低量化CSP（QCSP）从Pspace到NP的复杂性的属性。相比之下，我们确定了VCSP易于处理但QVCSP难以处理Pspace的某些类型的问题。作为主要推论，我们推导了布尔语言QCSP的Shaeffer二分法在P和Pspace之间的类似物，以及Cohen等人。布尔值语言上的VCSP的P和NP-complete之间的二分法：我们证明QVCSP遵循P和Pspace-complete之间的二分法。最后，我们展示了大小为3或更大的域的NP完全QVCSP的示例，这对于QVCSP而言，充其量是P，NP完全和Pspace完全之间的三分法。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号