• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>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）的量化和值延伸的复杂性。该问题也称为MIN-MAX量子的加权约束满足问题[1]。保护语言的多体形是我们分析的起点。我们建立一些QVCSP通过制定新算法或通过延长崩溃的使用来解决多项式时间的情况，该性能熟知用于将量化的CSP（QCSP）的复杂性从PSPACE降低到NP。相比之下，我们确定VCSP易于遗传的一些问题，但QVCSP是PSPACE-HARD。作为主要的推论，我们在Boolean语言和Cohen等人的QCSP之间获得了Shaeffer二分法的类似物。 P和NP-Complety之间的二分法，用于布尔值的语言上的VCSP：我们证明QVCSP在P和PSPace完整之间遵循二分法。最后，我们显示出NP完全QVCSP的例子为大小3和多个结构域，这表明在P，NP完全和PSPACE完成用于QVCSP之间最好一个三分法。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号