《计算机科学》上姜新文的NP=P证明靠谱吗？

水木社区手机版

主题:《计算机科学》上姜新文的NP=P证明靠谱吗？
10楼|z16166|2020-08-04 23:37:35|只看此ID
https://mp.weixin.qq.com/s/o9HLAufA8VzgK9iDgOYe9A
--
FROM 125.35.121.*
11楼|gtgtjing|2020-08-04 23:52:50|只看此ID
因为哈密顿图判定问题是NP完全问题，而任何NP完全问题有多项式时间算法，则有NP=P是普天下所有相关课本和著作的定理

这句话什么意思
【在 z16166 的大作中提到: 】
: https://mp.weixin.qq.com/s/o9HLAufA8VzgK9iDgOYe9A
--
FROM 123.113.83.*
12楼|gnwd|2020-08-04 23:55:04|只看此ID
还是没说论文内容
哪天看看，谁把算法贴上来
不会这么多人都一直嚷嚷，但就是没人看吧

【在 z16166 的大作中提到: 】
:
: https://mp.weixin.qq.com/s/o9HLAufA8VzgK9iDgOYe9A
--
FROM 125.86.90.*
13楼|gnwd|2020-08-05 00:04:17|只看此ID
这段话不清晰

就是所有的NP问题中，有一类问题，被称为NPC问题，Cook曾经证明过，所有的NP问题都可以被规约为合取范式的可满足性问题，这样一来，如果合取范式的可满足性问题有多项式时间的解，那所有的已知的未知的NP问题，都将有多项式时间的解。除了这个合取范式的问题，后来陆陆续续证明了很多问题也是NPC问题，于是，在这么多NPC问题中，只要有一个有突破，所有的NP问题都将有多项式时间算法

【在 gtgtjing 的大作中提到: 】
:
: 因为哈密顿图判定问题是NP完全问题，而任何NP完全问题有多项式时间算法，则有NP=P是普天下所有相关课本和著作的定理
:
: 这句话什么意思
: 【在 z16166 的大作中提到: 】
--
FROM 125.86.90.*
14楼|zhuxf|2020-08-05 06:35:31|只看此ID
嗯，姜先把npc抛出来，结果话锋一转，开始说np。姜到底是说npc还是np呢？不知所云。
cook有一篇经典论文我看过，基本上都是讲npc的。不知道姜说的‘cook曾经证明过’是cook的哪一篇论文证明过
【在 gnwd 的大作中提到: 】
: 这段话不清晰
:
: 就是所有的NP问题中，有一类问题，被称为NPC问题，Cook曾经证明过，所有的NP问题都可以被规约为合取范式的可满足性问题，这样一来，如果合取范式的可满足性问题有多项式时间的解，那所有的已知的未知的NP问题，都将有多项式时间的解。除了这个合取范式的问题，后来陆陆续续证明了很多问题也是NPC问题，于是，在这么多NPC问题中，只要有一个有突破，所有的NP问题都将有多项式时间算法
: ...................
--
FROM 221.216.143.*
15楼|koalakd|2020-08-05 08:11:59|只看此ID
这么多年他还是没有放弃啊。除了执着于这个问题，其他都还挺靠谱。
--
FROM 49.94.142.*
16楼|wenzhongzi|2020-08-05 20:43:40|只看此ID
百分之99.99999%不靠谱

【在 gtgtjing 的大作中提到: 】
:
: 懂这个的大牛来说说
:

#发自zSMTH@PBAM00
--
FROM 223.104.3.*
17楼|thinkingreed|2020-08-14 13:17:03|只看此ID
这人的证明肯定有问题。
但他不是不懂得NP=P？这个问题。
你们几个不明白，不会去查查看看吗？
【在 zhuxf 的大作中提到: 】
: 嗯，姜先把npc抛出来，结果话锋一转，开始说np。姜到底是说npc还是np呢？不知所云。
: cook有一篇经典论文我看过，基本上都是讲npc的。不知道姜说的‘cook曾经证明过’是cook的哪一篇论文证明过
--
FROM 183.228.218.*