In the search for a logic capturing polynomial time the most promising candidates are Choiceless Polynomial Time (CPT) and rank logic. Rank logic extends fixed-point logic with counting by a rank operator over prime fields. We show that the isomorphism problem for CFI graphs over $\mathbb{Z}_{2^i}$ cannot be defined in rank logic, even if the base graph is totally ordered. However, CPT can define this isomorphism problem. We thereby separate rank logic from CPT and in particular from polynomial time.


翻译:在寻找掌握多元时间的逻辑时,最有前途的候选人是无选择的多元时间(CPT)和级级逻辑。 Rian逻辑将固定点逻辑延伸至由一个级操作员对黄金田进行计数。我们显示,即使基本图表完全按顺序排列,CFI图表的等值逻辑也无法界定CFI图表的等式问题。然而,CPT可以定义这个无形态问题。我们因此将等级逻辑与CPT,特别是多元时间区分开来。

0
下载
关闭预览

相关内容

【干货书】机器学习速查手册,135页pdf
专知会员服务
122+阅读 · 2020年11月20日
Linux导论,Introduction to Linux,96页ppt
专知会员服务
76+阅读 · 2020年7月26日
专知会员服务
137+阅读 · 2020年5月19日
【经典书】贝叶斯编程,378页pdf,Bayesian Programming
专知会员服务
244+阅读 · 2020年5月18日
Fariz Darari简明《博弈论Game Theory》介绍,35页ppt
专知会员服务
106+阅读 · 2020年5月15日
【CVPR2020-Facebook AI】前置不变表示的自监督学习
专知会员服务
46+阅读 · 2020年4月19日
【文本匹配】Question Answering论文
深度学习自然语言处理
8+阅读 · 2020年4月20日
分布式并行架构Ray介绍
CreateAMind
9+阅读 · 2019年8月9日
Transferring Knowledge across Learning Processes
CreateAMind
26+阅读 · 2019年5月18日
sklearn 与分类算法
人工智能头条
7+阅读 · 2019年3月12日
无监督元学习表示学习
CreateAMind
26+阅读 · 2019年1月4日
ResNet, AlexNet, VGG, Inception:各种卷积网络架构的理解
全球人工智能
19+阅读 · 2017年12月17日
【学习】(Python)SVM数据分类
机器学习研究会
6+阅读 · 2017年10月15日
【学习】Hierarchical Softmax
机器学习研究会
4+阅读 · 2017年8月6日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
Arxiv
0+阅读 · 2021年8月19日
Arxiv
4+阅读 · 2019年2月8日
Implicit Maximum Likelihood Estimation
Arxiv
7+阅读 · 2018年9月24日
VIP会员
相关VIP内容
【干货书】机器学习速查手册,135页pdf
专知会员服务
122+阅读 · 2020年11月20日
Linux导论,Introduction to Linux,96页ppt
专知会员服务
76+阅读 · 2020年7月26日
专知会员服务
137+阅读 · 2020年5月19日
【经典书】贝叶斯编程,378页pdf,Bayesian Programming
专知会员服务
244+阅读 · 2020年5月18日
Fariz Darari简明《博弈论Game Theory》介绍,35页ppt
专知会员服务
106+阅读 · 2020年5月15日
【CVPR2020-Facebook AI】前置不变表示的自监督学习
专知会员服务
46+阅读 · 2020年4月19日
相关资讯
【文本匹配】Question Answering论文
深度学习自然语言处理
8+阅读 · 2020年4月20日
分布式并行架构Ray介绍
CreateAMind
9+阅读 · 2019年8月9日
Transferring Knowledge across Learning Processes
CreateAMind
26+阅读 · 2019年5月18日
sklearn 与分类算法
人工智能头条
7+阅读 · 2019年3月12日
无监督元学习表示学习
CreateAMind
26+阅读 · 2019年1月4日
ResNet, AlexNet, VGG, Inception:各种卷积网络架构的理解
全球人工智能
19+阅读 · 2017年12月17日
【学习】(Python)SVM数据分类
机器学习研究会
6+阅读 · 2017年10月15日
【学习】Hierarchical Softmax
机器学习研究会
4+阅读 · 2017年8月6日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
Top
微信扫码咨询专知VIP会员