会员服务
CC · 分离的 · 示例 ·
2021 年 8 月 29 日
Scheme-theoretic Approach to Computational Complexity I. The Separation of P and NP
翻译：计算复杂程度一. P和NP的分离
Ali Çivril
Ali Çivril

We lay the foundations of a new theory for algorithms and computational complexity by parameterizing the instances of a computational problem as a moduli scheme. Considering the geometry of the scheme associated to 3-SAT, we separate P and NP.


翻译：我们通过将计算问题实例作为模式方案参数化,为算法和计算复杂性的新理论打下基础。 考虑到与3SAT相关计划的几何性,我们将P和NP分开。
1
下载
关闭预览

相关内容

CC在计算复杂性方面表现突出。它的学科处于数学与计算机理论科学的交叉点，具有清晰的数学轮廓和严格的数学格式。官网链接：https://link.springer.com/journal/37
《算法凸几何》简明书，Algorithmic Convex Geometry，50页pdf
专知会员服务
41+阅读 · 2021年4月2日
INRIA最新「机器学习理论」新书，229页pdf原理性阐述机器学习
INRIA最新「机器学习理论」新书，229页pdf原理性阐述机器学习
专知会员服务
67+阅读 · 2021年3月27日
【经典书】计算最优传输，209页pdf，Computational Optimal Transport
【经典书】计算最优传输，209页pdf，Computational Optimal Transport
专知会员服务
74+阅读 · 2021年1月10日
Fariz Darari简明《博弈论Game Theory》介绍，35页ppt
Fariz Darari简明《博弈论Game Theory》介绍，35页ppt
专知会员服务
109+阅读 · 2020年5月15日
【IPAM 】张量主元分析中的高维成本景观和梯度下降及其推广（High-dimensional cost landscape and gradient descent in Tensor PCA and its generalisations），附41页pdf
【IPAM 】张量主元分析中的高维成本景观和梯度下降及其推广（High-dimensional cost landscape and gradient descent in Tensor PCA and its generalisations），附41页pdf
专知会员服务
12+阅读 · 2019年11月22日
【北京智源大会2019】 神经网络的优化Optimization for Overparametrized Deep Neural Networks，北京大学 | 王立威
【北京智源大会2019】 神经网络的优化Optimization for Overparametrized Deep Neural Networks，北京大学 | 王立威
专知会员服务
22+阅读 · 2019年11月21日
【电子书】人工智能编程范式（Paradigms of Artificial Intelligence Programming）1048页PDF免费下载
【电子书】人工智能编程范式（Paradigms of Artificial Intelligence Programming）1048页PDF免费下载
专知会员服务
47+阅读 · 2019年10月30日
Auto-Sizing the Transformer Network: Improving Speed, Efficiency, and Performance for Low-Resource Machine Translation
Auto-Sizing the Transformer Network: Improving Speed, Efficiency, and Performance for Low-Resource Machine Translation
专知会员服务
47+阅读 · 2019年10月17日
Deep Learning Based Detection and Correction of Cardiac MR Motion Artefacts During Reconstruction for High-Quality Segmentation
Deep Learning Based Detection and Correction of Cardiac MR Motion Artefacts During Reconstruction for High-Quality Segmentation
专知会员服务
56+阅读 · 2019年10月17日
【新书】Python编程基础，669页pdf
【新书】Python编程基础，669页pdf
专知会员服务
193+阅读 · 2019年10月10日
【经典书】计算最优传输，209页pdf，Computational Optimal Transport
【经典书】计算最优传输，209页pdf，Computational Optimal Transport
专知
15+阅读 · 2021年1月10日
【NIPS2019】Infidelity and Sensitivity：模型可解释性方法的定量评估
【NIPS2019】Infidelity and Sensitivity：模型可解释性方法的定量评估
AINLP
19+阅读 · 2020年6月14日
图机器学习 2.2-2.4 Properties of Networks, Random Graph
图机器学习 2.2-2.4 Properties of Networks, Random Graph
图与推荐
10+阅读 · 2020年3月28日
meta learning 17年：MAML SNAIL
meta learning 17年：MAML SNAIL
CreateAMind
11+阅读 · 2019年1月2日
大数据 | 顶级SCI期刊专刊/国际会议信息7条
大数据 | 顶级SCI期刊专刊/国际会议信息7条
Call4Papers
10+阅读 · 2018年12月29日
CCF C类 | IJCNN 2019 Special Section : 信息论与深度学习
CCF C类 | IJCNN 2019 Special Section : 信息论与深度学习
Call4Papers
5+阅读 · 2018年12月7日
Hierarchical Disentangled Representations
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
【推荐】免费书(草稿)：数据科学的数学基础
【推荐】免费书(草稿)：数据科学的数学基础
机器学习研究会
20+阅读 · 2017年10月1日
【推荐】决策树/随机森林深入解析
【推荐】决策树/随机森林深入解析
机器学习研究会
5+阅读 · 2017年9月21日
强化学习 cartpole_a3c
强化学习 cartpole_a3c
CreateAMind
9+阅读 · 2017年7月21日
A hyper-reduced MAC scheme for the parametric Stokes and Navier-Stokes equations
Arxiv
0+阅读 · 2021年10月21日
WENO interpolations and reconstructions using data bounded polynomial approximation
Arxiv
0+阅读 · 2021年10月21日
Adaptive Gradient Descent for Optimal Control of Parabolic Equations with Random Parameters
Arxiv
0+阅读 · 2021年10月20日
The complexity of approximating the complex-valued Ising model on bounded degree graphs
Arxiv
0+阅读 · 2021年10月20日
Worst-Case Efficient Dynamic Geometric Independent Set
Arxiv
0+阅读 · 2021年10月18日
Maximal Spaces for Approximation Rates in $\ell^1$-regularization
Arxiv
0+阅读 · 2021年10月18日
Independent Approximates enable closed-form parameter estimation of heavy-tailed distributions
Arxiv
0+阅读 · 2021年10月16日
Loosely coupled, non-iterative time-splitting scheme based on Robin-Robin coupling: unified analysis for parabolic/parabolic and parabolic/hyperbolic problems
Loosely coupled, non-iterative time-splitting scheme based on Robin-Robin coupling: unified analysis for parabolic/parabolic and parabolic/hyperbolic problems
Arxiv
0+阅读 · 2021年10月15日
Strategyproof Mechanisms For Group-Fair Facility Location Problems
Arxiv
0+阅读 · 2021年10月15日
Classical symmetries and the Quantum Approximate Optimization Algorithm
Arxiv
0+阅读 · 2021年10月8日
VIP会员
文章信息
前往arXiv
下载PDF
相关主题
CC
分离的
示例
相关VIP内容
《算法凸几何》简明书，Algorithmic Convex Geometry，50页pdf
专知会员服务
41+阅读 · 2021年4月2日
INRIA最新「机器学习理论」新书，229页pdf原理性阐述机器学习
INRIA最新「机器学习理论」新书，229页pdf原理性阐述机器学习
专知会员服务
67+阅读 · 2021年3月27日
【经典书】计算最优传输，209页pdf，Computational Optimal Transport
【经典书】计算最优传输，209页pdf，Computational Optimal Transport
专知会员服务
74+阅读 · 2021年1月10日
Fariz Darari简明《博弈论Game Theory》介绍，35页ppt
Fariz Darari简明《博弈论Game Theory》介绍，35页ppt
专知会员服务
109+阅读 · 2020年5月15日
【IPAM 】张量主元分析中的高维成本景观和梯度下降及其推广（High-dimensional cost landscape and gradient descent in Tensor PCA and its generalisations），附41页pdf
【IPAM 】张量主元分析中的高维成本景观和梯度下降及其推广（High-dimensional cost landscape and gradient descent in Tensor PCA and its generalisations），附41页pdf
专知会员服务
12+阅读 · 2019年11月22日
【北京智源大会2019】 神经网络的优化Optimization for Overparametrized Deep Neural Networks，北京大学 | 王立威
【北京智源大会2019】 神经网络的优化Optimization for Overparametrized Deep Neural Networks，北京大学 | 王立威
专知会员服务
22+阅读 · 2019年11月21日
【电子书】人工智能编程范式（Paradigms of Artificial Intelligence Programming）1048页PDF免费下载
【电子书】人工智能编程范式（Paradigms of Artificial Intelligence Programming）1048页PDF免费下载
专知会员服务
47+阅读 · 2019年10月30日
Auto-Sizing the Transformer Network: Improving Speed, Efficiency, and Performance for Low-Resource Machine Translation
Auto-Sizing the Transformer Network: Improving Speed, Efficiency, and Performance for Low-Resource Machine Translation
专知会员服务
47+阅读 · 2019年10月17日
Deep Learning Based Detection and Correction of Cardiac MR Motion Artefacts During Reconstruction for High-Quality Segmentation
Deep Learning Based Detection and Correction of Cardiac MR Motion Artefacts During Reconstruction for High-Quality Segmentation
专知会员服务
56+阅读 · 2019年10月17日
【新书】Python编程基础，669页pdf
【新书】Python编程基础，669页pdf
专知会员服务
193+阅读 · 2019年10月10日
热门VIP内容
相关资讯
【经典书】计算最优传输，209页pdf，Computational Optimal Transport
【经典书】计算最优传输，209页pdf，Computational Optimal Transport
专知
15+阅读 · 2021年1月10日
【NIPS2019】Infidelity and Sensitivity：模型可解释性方法的定量评估
【NIPS2019】Infidelity and Sensitivity：模型可解释性方法的定量评估
AINLP
19+阅读 · 2020年6月14日
图机器学习 2.2-2.4 Properties of Networks, Random Graph
图机器学习 2.2-2.4 Properties of Networks, Random Graph
图与推荐
10+阅读 · 2020年3月28日
meta learning 17年：MAML SNAIL
meta learning 17年：MAML SNAIL
CreateAMind
11+阅读 · 2019年1月2日
大数据 | 顶级SCI期刊专刊/国际会议信息7条
大数据 | 顶级SCI期刊专刊/国际会议信息7条
Call4Papers
10+阅读 · 2018年12月29日
CCF C类 | IJCNN 2019 Special Section : 信息论与深度学习
CCF C类 | IJCNN 2019 Special Section : 信息论与深度学习
Call4Papers
5+阅读 · 2018年12月7日
Hierarchical Disentangled Representations
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
【推荐】免费书(草稿)：数据科学的数学基础
【推荐】免费书(草稿)：数据科学的数学基础
机器学习研究会
20+阅读 · 2017年10月1日
【推荐】决策树/随机森林深入解析
【推荐】决策树/随机森林深入解析
机器学习研究会
5+阅读 · 2017年9月21日
强化学习 cartpole_a3c
强化学习 cartpole_a3c
CreateAMind
9+阅读 · 2017年7月21日
相关论文
A hyper-reduced MAC scheme for the parametric Stokes and Navier-Stokes equations
Arxiv
0+阅读 · 2021年10月21日
WENO interpolations and reconstructions using data bounded polynomial approximation
Arxiv
0+阅读 · 2021年10月21日
Adaptive Gradient Descent for Optimal Control of Parabolic Equations with Random Parameters
Arxiv
0+阅读 · 2021年10月20日
The complexity of approximating the complex-valued Ising model on bounded degree graphs
Arxiv
0+阅读 · 2021年10月20日
Worst-Case Efficient Dynamic Geometric Independent Set
Arxiv
0+阅读 · 2021年10月18日
Maximal Spaces for Approximation Rates in $\ell^1$-regularization
Arxiv
0+阅读 · 2021年10月18日
Independent Approximates enable closed-form parameter estimation of heavy-tailed distributions
Arxiv
0+阅读 · 2021年10月16日
Loosely coupled, non-iterative time-splitting scheme based on Robin-Robin coupling: unified analysis for parabolic/parabolic and parabolic/hyperbolic problems
Loosely coupled, non-iterative time-splitting scheme based on Robin-Robin coupling: unified analysis for parabolic/parabolic and parabolic/hyperbolic problems
Arxiv
0+阅读 · 2021年10月15日
Strategyproof Mechanisms For Group-Fair Facility Location Problems
Arxiv
0+阅读 · 2021年10月15日
Classical symmetries and the Quantum Approximate Optimization Algorithm
Arxiv
0+阅读 · 2021年10月8日
Top
微信扫码咨询专知VIP会员
Top