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
专知会员服务
140+阅读 · 2021年3月17日
专知会员服务
76+阅读 · 2021年3月16日
【干货书】机器学习速查手册,135页pdf
专知会员服务
124+阅读 · 2020年11月20日
【干货书】计算机科学离散数学,627页pdf
专知会员服务
130+阅读 · 2020年8月31日
MIT新书《强化学习与最优控制》
专知会员服务
273+阅读 · 2019年10月9日
已删除
将门创投
4+阅读 · 2020年1月6日
Ray RLlib: Scalable 降龙十八掌
CreateAMind
9+阅读 · 2018年12月28日
Disentangled的假设的探讨
CreateAMind
9+阅读 · 2018年12月10日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
lightgbm algorithm case of kaggle(上)
R语言中文社区
8+阅读 · 2018年3月20日
Arxiv
0+阅读 · 2021年9月16日
VIP会员
相关VIP内容
专知会员服务
140+阅读 · 2021年3月17日
专知会员服务
76+阅读 · 2021年3月16日
【干货书】机器学习速查手册,135页pdf
专知会员服务
124+阅读 · 2020年11月20日
【干货书】计算机科学离散数学,627页pdf
专知会员服务
130+阅读 · 2020年8月31日
MIT新书《强化学习与最优控制》
专知会员服务
273+阅读 · 2019年10月9日
相关资讯
已删除
将门创投
4+阅读 · 2020年1月6日
Ray RLlib: Scalable 降龙十八掌
CreateAMind
9+阅读 · 2018年12月28日
Disentangled的假设的探讨
CreateAMind
9+阅读 · 2018年12月10日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
lightgbm algorithm case of kaggle(上)
R语言中文社区
8+阅读 · 2018年3月20日
Top
微信扫码咨询专知VIP会员