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
下载
关闭预览

相关内容

【杜克-Bhuwan Dhingra】语言模型即知识图谱,46页ppt
专知会员服务
65+阅读 · 2021年11月15日
专知会员服务
50+阅读 · 2021年6月30日
专知会员服务
42+阅读 · 2020年12月18日
Linux导论,Introduction to Linux,96页ppt
专知会员服务
77+阅读 · 2020年7月26日
MIT-深度学习Deep Learning State of the Art in 2020,87页ppt
专知会员服务
61+阅读 · 2020年2月17日
最新BERT相关论文清单,BERT-related Papers
专知会员服务
52+阅读 · 2019年9月29日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
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日
漆桂林 | 开放:知识图谱发展的必由之路
开放知识图谱
7+阅读 · 2017年6月28日
Arxiv
0+阅读 · 2021年12月14日
Arxiv
14+阅读 · 2020年12月17日
Arxiv
3+阅读 · 2018年2月24日
VIP会员
相关VIP内容
【杜克-Bhuwan Dhingra】语言模型即知识图谱,46页ppt
专知会员服务
65+阅读 · 2021年11月15日
专知会员服务
50+阅读 · 2021年6月30日
专知会员服务
42+阅读 · 2020年12月18日
Linux导论,Introduction to Linux,96页ppt
专知会员服务
77+阅读 · 2020年7月26日
MIT-深度学习Deep Learning State of the Art in 2020,87页ppt
专知会员服务
61+阅读 · 2020年2月17日
最新BERT相关论文清单,BERT-related Papers
专知会员服务
52+阅读 · 2019年9月29日
相关资讯
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
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日
漆桂林 | 开放:知识图谱发展的必由之路
开放知识图谱
7+阅读 · 2017年6月28日
Top
微信扫码咨询专知VIP会员