会员服务
NPC · 可约的 · SimPLe · SAT · 图 ·
2021 年 8 月 9 日
A Polynomial Time Algorithm for a NPC Problem
翻译：NPC 问题聚合时间的算法
Xinwen Jiang
Xinwen Jiang
from arxiv, 13 pages,7 figures

It is introduced a so called 'Multi-stage graph Simple Path' problem (MSP for short) and proved that SAT problem can be polynomial reducible to MSP problem in this small paper. To solve MSP problem, we propose a polynomial time algorithm. Our result implies NP=P.


翻译：它被引入了所谓的“多阶段图形简单路径”问题(MSP简称MSP ), 并证明SAT问题可以在这份小文件中为MSP问题提供多级缩写。 为了解决MSP问题, 我们建议采用一个多级时间算法。 我们的结果意味着NP=P 。
0
下载
关闭预览

相关内容

NPC：IFIP International Conference on Network and Parallel Computing。 Explanation：网络与并行计算国际会议。 Publisher：Springer。 SIT： http://dblp.uni-trier.de/db/conf/npc/
【深度学习社区检测】Deep Learning for Community Detection: Progress, Challenges and Opportunities
【深度学习社区检测】Deep Learning for Community Detection: Progress, Challenges and Opportunities
专知会员服务
27+阅读 · 2020年6月13日
【经典书】贝叶斯编程，378页pdf，Bayesian Programming
【经典书】贝叶斯编程，378页pdf，Bayesian Programming
专知会员服务
247+阅读 · 2020年5月18日
随机特征核近似综述: 算法与理论，Random Features for Kernel Approximation: A Survey in Algorithms, Theory, and Beyond
随机特征核近似综述: 算法与理论，Random Features for Kernel Approximation: A Survey in Algorithms, Theory, and Beyond
专知会员服务
32+阅读 · 2020年4月26日
【硬核书】数学博弈论与应用，431页pdf，Mathematical Game Theory and Applications
【硬核书】数学博弈论与应用，431页pdf，Mathematical Game Theory and Applications
专知会员服务
166+阅读 · 2020年4月18日
图像分类技巧集，17页ppt《Bag of Tricks for Image Classification》
图像分类技巧集，17页ppt《Bag of Tricks for Image Classification》
专知会员服务
94+阅读 · 2020年3月12日
康奈尔大学Jon Kleinberg经典书《算法设计Algorithm Design》课件PPT与电子书，864页pdf
康奈尔大学Jon Kleinberg经典书《算法设计Algorithm Design》课件PPT与电子书，864页pdf
专知会员服务
229+阅读 · 2020年1月21日
【论文】深度学习的最优化:理论和算法（Optimization for deep learning: theory and algorithms）
【论文】深度学习的最优化:理论和算法（Optimization for deep learning: theory and algorithms）
专知会员服务
146+阅读 · 2019年12月28日
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日
Connections between Support Vector Machines, Wasserstein distance and gradient-penalty GANs
Connections between Support Vector Machines, Wasserstein distance and gradient-penalty GANs
专知会员服务
34+阅读 · 2019年10月17日
【加州大学伯克利分校博士论文】通过自我监督预测学习泛化
【加州大学伯克利分校博士论文】通过自我监督预测学习泛化
专知会员服务
64+阅读 · 2019年10月9日
已删除
已删除
将门创投
7+阅读 · 2018年4月25日
Polynomial Turing Kernels for Clique with an Optimal Number of Queries
Arxiv
0+阅读 · 2021年10月7日
Faster algorithm for Unique $(k,2)$-CSP
Arxiv
0+阅读 · 2021年10月7日
Fixed-Parameter Algorithms for Longest Heapable Subsequence and Maximum Binary Tree
Arxiv
0+阅读 · 2021年10月6日
Parameterized Algorithms for the Steiner Tree Problem on a Directed Hypercube
Arxiv
0+阅读 · 2021年10月6日
More on Change-Making and Related Problems
Arxiv
0+阅读 · 2021年10月6日
Jacobi-type algorithms for homogeneous polynomial optimization on Stiefel manifolds with applications to tensor approximations
Arxiv
0+阅读 · 2021年10月5日
The Limits of Optimal Pricing in the Dark
Arxiv
0+阅读 · 2021年10月4日
Implicit Maximum Likelihood Estimation
Implicit Maximum Likelihood Estimation
Arxiv
7+阅读 · 2018年9月24日
A fast algorithm with minimax optimal guarantees for topic models with an unknown number of topics
Arxiv
7+阅读 · 2018年6月12日
(FPT-)Approximation Algorithms for the Virtual Network Embedding Problem
Arxiv
4+阅读 · 2018年3月12日
VIP会员
文章信息
前往arXiv
下载PDF
相关主题
NPC
可约的
SimPLe
SAT
图
相关VIP内容
【深度学习社区检测】Deep Learning for Community Detection: Progress, Challenges and Opportunities
【深度学习社区检测】Deep Learning for Community Detection: Progress, Challenges and Opportunities
专知会员服务
27+阅读 · 2020年6月13日
【经典书】贝叶斯编程，378页pdf，Bayesian Programming
【经典书】贝叶斯编程，378页pdf，Bayesian Programming
专知会员服务
247+阅读 · 2020年5月18日
随机特征核近似综述: 算法与理论，Random Features for Kernel Approximation: A Survey in Algorithms, Theory, and Beyond
随机特征核近似综述: 算法与理论，Random Features for Kernel Approximation: A Survey in Algorithms, Theory, and Beyond
专知会员服务
32+阅读 · 2020年4月26日
【硬核书】数学博弈论与应用，431页pdf，Mathematical Game Theory and Applications
【硬核书】数学博弈论与应用，431页pdf，Mathematical Game Theory and Applications
专知会员服务
166+阅读 · 2020年4月18日
图像分类技巧集，17页ppt《Bag of Tricks for Image Classification》
图像分类技巧集，17页ppt《Bag of Tricks for Image Classification》
专知会员服务
94+阅读 · 2020年3月12日
康奈尔大学Jon Kleinberg经典书《算法设计Algorithm Design》课件PPT与电子书，864页pdf
康奈尔大学Jon Kleinberg经典书《算法设计Algorithm Design》课件PPT与电子书，864页pdf
专知会员服务
229+阅读 · 2020年1月21日
【论文】深度学习的最优化:理论和算法（Optimization for deep learning: theory and algorithms）
【论文】深度学习的最优化:理论和算法（Optimization for deep learning: theory and algorithms）
专知会员服务
146+阅读 · 2019年12月28日
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日
Connections between Support Vector Machines, Wasserstein distance and gradient-penalty GANs
Connections between Support Vector Machines, Wasserstein distance and gradient-penalty GANs
专知会员服务
34+阅读 · 2019年10月17日
【加州大学伯克利分校博士论文】通过自我监督预测学习泛化
【加州大学伯克利分校博士论文】通过自我监督预测学习泛化
专知会员服务
64+阅读 · 2019年10月9日
热门VIP内容
相关资讯
已删除
已删除
将门创投
7+阅读 · 2018年4月25日
相关论文
Polynomial Turing Kernels for Clique with an Optimal Number of Queries
Arxiv
0+阅读 · 2021年10月7日
Faster algorithm for Unique $(k,2)$-CSP
Arxiv
0+阅读 · 2021年10月7日
Fixed-Parameter Algorithms for Longest Heapable Subsequence and Maximum Binary Tree
Arxiv
0+阅读 · 2021年10月6日
Parameterized Algorithms for the Steiner Tree Problem on a Directed Hypercube
Arxiv
0+阅读 · 2021年10月6日
More on Change-Making and Related Problems
Arxiv
0+阅读 · 2021年10月6日
Jacobi-type algorithms for homogeneous polynomial optimization on Stiefel manifolds with applications to tensor approximations
Arxiv
0+阅读 · 2021年10月5日
The Limits of Optimal Pricing in the Dark
Arxiv
0+阅读 · 2021年10月4日
Implicit Maximum Likelihood Estimation
Implicit Maximum Likelihood Estimation
Arxiv
7+阅读 · 2018年9月24日
A fast algorithm with minimax optimal guarantees for topic models with an unknown number of topics
Arxiv
7+阅读 · 2018年6月12日
(FPT-)Approximation Algorithms for the Virtual Network Embedding Problem
Arxiv
4+阅读 · 2018年3月12日
Top
微信扫码咨询专知VIP会员
Top