看帖神器
未名空间
追帖动态
头条新闻
每日新帖
最新热帖
新闻存档
热帖存档
文学城
虎扑论坛
未名空间
北美华人网
北美微论坛
看帖神器
登录
← 下载
《看帖神器》官方
iOS App
,体验轻松追帖。
P真的等于NP了,in a sense
查看未名空间今日新帖
最新回复:2020年12月26日 17点49分 PT
共 (4) 楼
返回列表
订阅追帖
只看未读
更多选项
阅读全帖
只看图片
只看视频
查看原帖
T
TheMatrix
接近 4 年
楼主 (未名空间)
我这么表述一下想法吧。比如说邮差问题,
1,每一个邮差问题,即每一个目的地坐标都给定的邮差问题,都有P的解法。
比如有100个目的地,坐标都给定。简单枚举法时间复杂度为100! 量级。而我说一定有p(100)时间复杂度的解法。但是这个解法高度依赖于这100个点的坐标,换一套值就得
换一个解法。
这算不算对问题的一种消解?没有统一的P解法,但是每一个具体的问题都有一个P解法。
2,问题空间partition还可以合并。每一个具体的邮差问题,都有一个P解法,不仅覆
盖这个问题,还能覆盖周围的问题。
3,但总是不能全覆盖general邮差问题的问题空间。
a
aaddoo
接近 4 年
2 楼
P不等于NP,因为NP问题的熵值大于P问题的熵值。
T
TheMatrix
接近 4 年
3 楼
你这直接就力迫证明了。
【 在 aaddoo (nothing) 的大作中提到: 】
: P不等于NP,因为NP问题的熵值大于P问题的熵值。
i
iDemocracy
接近 4 年
4 楼
外行不要浪费时间了,比起半个世纪之前,现在仅仅弄懂问题是什么就得花个三五年研究时间。
请输入帖子链接
收藏帖子
我这么表述一下想法吧。比如说邮差问题,
1,每一个邮差问题,即每一个目的地坐标都给定的邮差问题,都有P的解法。
比如有100个目的地,坐标都给定。简单枚举法时间复杂度为100! 量级。而我说一定有p(100)时间复杂度的解法。但是这个解法高度依赖于这100个点的坐标,换一套值就得
换一个解法。
这算不算对问题的一种消解?没有统一的P解法,但是每一个具体的问题都有一个P解法。
2,问题空间partition还可以合并。每一个具体的邮差问题,都有一个P解法,不仅覆
盖这个问题,还能覆盖周围的问题。
3,但总是不能全覆盖general邮差问题的问题空间。
P不等于NP,因为NP问题的熵值大于P问题的熵值。
你这直接就力迫证明了。
【 在 aaddoo (nothing) 的大作中提到: 】
: P不等于NP,因为NP问题的熵值大于P问题的熵值。
外行不要浪费时间了,比起半个世纪之前,现在仅仅弄懂问题是什么就得花个三五年研究时间。