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
专知会员服务
76+阅读 · 2021年3月16日
专知会员服务
50+阅读 · 2020年12月14日
专知会员服务
84+阅读 · 2020年12月5日
【干货书】机器学习速查手册,135页pdf
专知会员服务
125+阅读 · 2020年11月20日
专知会员服务
52+阅读 · 2020年9月7日
意识是一种数学模式
CreateAMind
3+阅读 · 2019年6月24日
人工智能 | ACCV 2020等国际会议信息5条
Call4Papers
6+阅读 · 2019年6月21日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
人工智能训练师的再定义
竹间智能Emotibot
10+阅读 · 2019年5月15日
面试时让你手推公式不在害怕 | 线性回归
计算机视觉life
4+阅读 · 2019年1月18日
CCCF专栏 | 从2018年的戈登•贝尔奖说起
中国计算机学会
10+阅读 · 2019年1月17日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
已删除
将门创投
4+阅读 · 2018年11月6日
Arxiv
0+阅读 · 2021年11月5日
Arxiv
3+阅读 · 2018年2月24日
VIP会员
相关资讯
意识是一种数学模式
CreateAMind
3+阅读 · 2019年6月24日
人工智能 | ACCV 2020等国际会议信息5条
Call4Papers
6+阅读 · 2019年6月21日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
人工智能训练师的再定义
竹间智能Emotibot
10+阅读 · 2019年5月15日
面试时让你手推公式不在害怕 | 线性回归
计算机视觉life
4+阅读 · 2019年1月18日
CCCF专栏 | 从2018年的戈登•贝尔奖说起
中国计算机学会
10+阅读 · 2019年1月17日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
已删除
将门创投
4+阅读 · 2018年11月6日
Top
微信扫码咨询专知VIP会员