It is known that if an algebra of polymorphisms of the constraint language has the Polynomially Generated Powers (PGP) Property then the Quantified CSP can be reduced to the CSP over the same constraint language with constants. The only limitation of this reduction is that it is applicable only for the constraint languages with constants. We drastically simplified the reduction and generalized it for constraint languages without constants. As a result, we completely classified the complexity of the QCSP for constraint languages having the PGP property.


翻译:众所周知,如果约束语言多形态的代数具有多种族生成力特性,那么量化的CSP可以与固定不变的同一约束语言压缩到CSP, 唯一的限制是,这一减少只适用于有常数的制约语言。我们大幅度简化了限制语言的缩放,并将其推广到没有常数的制约语言。因此,我们完全区分了QCSP的复杂性,以限制具有PGP属性的语言。

0
下载
关闭预览

相关内容

专知会员服务
45+阅读 · 2020年12月18日
MIT-深度学习Deep Learning State of the Art in 2020,87页ppt
专知会员服务
62+阅读 · 2020年2月17日
Transferring Knowledge across Learning Processes
CreateAMind
29+阅读 · 2019年5月18日
spinningup.openai 强化学习资源完整
CreateAMind
6+阅读 · 2018年12月17日
Hierarchical Imitation - Reinforcement Learning
CreateAMind
19+阅读 · 2018年5月25日
视觉机械臂 visual-pushing-grasping
CreateAMind
3+阅读 · 2018年5月25日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
Arxiv
3+阅读 · 2018年2月24日
VIP会员
相关资讯
Transferring Knowledge across Learning Processes
CreateAMind
29+阅读 · 2019年5月18日
spinningup.openai 强化学习资源完整
CreateAMind
6+阅读 · 2018年12月17日
Hierarchical Imitation - Reinforcement Learning
CreateAMind
19+阅读 · 2018年5月25日
视觉机械臂 visual-pushing-grasping
CreateAMind
3+阅读 · 2018年5月25日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
Top
微信扫码咨询专知VIP会员