We show that the problem of determining the feasibility of quadratic systems over $\mathbb{C}$, $\mathbb{R}$, and $\mathbb{Z}$ requires exponential time. This separates P and NP over these fields/rings in the BCSS model of computation.


翻译:我们显示,确定四方形系统在$\mathbb{C}$、$\mathbb{R}$和$\mathbb{R}$是否可行的问题需要指数时间。这在BCSS计算模型中将P和NP区分在这些字段/环上。

0
下载
关闭预览

相关内容

CC在计算复杂性方面表现突出。它的学科处于数学与计算机理论科学的交叉点,具有清晰的数学轮廓和严格的数学格式。官网链接:https://link.springer.com/journal/37
专知会员服务
51+阅读 · 2020年12月14日
【2020新书】Python专业实践,250页pdf,Practices of the Python Pro
【新书】Python编程基础,669页pdf
专知会员服务
196+阅读 · 2019年10月10日
详解立体匹配系列经典SGM: (7) 弱纹理优化
计算机视觉life
12+阅读 · 2020年8月18日
分布式并行架构Ray介绍
CreateAMind
10+阅读 · 2019年8月9日
盘一盘 Python 系列 8 - Sklearn
平均机器
5+阅读 · 2019年5月30日
强化学习三篇论文 避免遗忘等
CreateAMind
20+阅读 · 2019年5月24日
人工智能 | 国际会议信息10条
Call4Papers
5+阅读 · 2018年12月18日
【学习】Hierarchical Softmax
机器学习研究会
4+阅读 · 2017年8月6日
Arxiv
0+阅读 · 2022年1月19日
Arxiv
0+阅读 · 2022年1月19日
VIP会员
相关VIP内容
专知会员服务
51+阅读 · 2020年12月14日
【2020新书】Python专业实践,250页pdf,Practices of the Python Pro
【新书】Python编程基础,669页pdf
专知会员服务
196+阅读 · 2019年10月10日
相关资讯
Top
微信扫码咨询专知VIP会员