In this paper we critique Keum-Bae Cho's proof that $\mathrm{P} \subsetneq \mathrm{NP}$. This proof relates instances of 3-SAT to indistinguishable binomial decision trees and claims that no polynomial-time algorithm can solve 3-SAT instances represented by these trees. We argue that their proof fails to justify a crucial step, and so the proof does not establish that $\mathrm{P} \subsetneq \mathrm{NP}$.


翻译:在本文中,我们批评了Keum-Bae Cho关于$\ mathrm{P}\ subsetneq\ mathrm{NP}$的证明。 这个证明将3SAT事件与无法区分的二元决定树联系起来, 并声称没有多元时算法可以解决由这些树代表的3SAT事件。 我们争辩说,它们的证据不能证明一个关键步骤是合理的, 所以证据不能证明$\ mathrm{P}\ subsetneq\ mathrm{NP}$ 。

0
下载
关闭预览

相关内容

专知会员服务
51+阅读 · 2020年12月14日
【硬核书】不完全信息决策理论,467页pdf
专知会员服务
359+阅读 · 2020年6月24日
可解释强化学习,Explainable Reinforcement Learning: A Survey
专知会员服务
131+阅读 · 2020年5月14日
强化学习最新教程,17页pdf
专知会员服务
181+阅读 · 2019年10月11日
[综述]深度学习下的场景文本检测与识别
专知会员服务
78+阅读 · 2019年10月10日
Hierarchically Structured Meta-learning
CreateAMind
27+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
29+阅读 · 2019年5月18日
【TED】生命中的每一年的智慧
英语演讲视频每日一推
10+阅读 · 2019年1月29日
强化学习的Unsupervised Meta-Learning
CreateAMind
18+阅读 · 2019年1月7日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
18+阅读 · 2018年12月24日
Disentangled的假设的探讨
CreateAMind
9+阅读 · 2018年12月10日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
【推荐】SVM实例教程
机器学习研究会
17+阅读 · 2017年8月26日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
Arxiv
0+阅读 · 2021年5月28日
Arxiv
0+阅读 · 2021年5月28日
Arxiv
0+阅读 · 2021年5月25日
Arxiv
3+阅读 · 2018年2月24日
VIP会员
相关主题
相关资讯
Hierarchically Structured Meta-learning
CreateAMind
27+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
29+阅读 · 2019年5月18日
【TED】生命中的每一年的智慧
英语演讲视频每日一推
10+阅读 · 2019年1月29日
强化学习的Unsupervised Meta-Learning
CreateAMind
18+阅读 · 2019年1月7日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
18+阅读 · 2018年12月24日
Disentangled的假设的探讨
CreateAMind
9+阅读 · 2018年12月10日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
【推荐】SVM实例教程
机器学习研究会
17+阅读 · 2017年8月26日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
Top
微信扫码咨询专知VIP会员