level 13
蹲人
2023年09月04日 07点09分
level 13
![[疑问]](/static/emoticons/u7591u95ee.png)
level 13
level 7
![[滑稽]](/static/emoticons/u6ed1u7a3d.png)
level 13
WarrnaCute
楼主
那我们来考虑解决一下单源哈密顿路径问题，只要能够在多项式时间复杂度内解决他那么枚举起点就能得到多项式时间复杂度的哈密顿通路问题的解法，从而证明P=NP
2023年09月04日 07点09分
5
level 13
level 13
level 7
level 13
WarrnaCute
楼主
我们考虑用网络流来解决掉这个问题，首先在原图上流量不太好跑，很容易有重有漏，所以我们把一个点拆成n层,然后中间是边双内部的边，然后在这个分层图上面构链就可以了![[呵呵]](/static/emoticons/u5475u5475.png)
2023年09月04日 07点09分
9
level 13
level 13
WarrnaCute
楼主
第一步是限制边数，先把边扯出来当点，然后所有边连汇点，这样子做明显是假的，第一步是重边无法保证，不过这个好处理，直接给所有的边一个代表点然后每一层的边都往代表点上面连一个流量为1的边
然后就没有重边了，然后还有一个很重要的就是我们要给边双一个代表点，把所有边的代表点送进边双里面，边双再往汇点连个流量是siz-1的，同时我们把所有点都向下一层的他们自己连边，最后一层连汇点以保证每一个点都被流到了
2023年09月04日 07点09分
11
然后就没有重边了，然后还有一个很重要的就是我们要给边双一个代表点，把所有边的代表点送进边双里面，边双再往汇点连个流量是siz-1的，同时我们把所有点都向下一层的他们自己连边，最后一层连汇点以保证每一个点都被流到了
level 13
WarrnaCute
楼主
我们现在已经保证了使用 siz-1 条边扩展 siz 个点，也就是说我们保证了这个形态是一个生成树，接下来我们将通过引入费用的方式限制他是一条链
2023年09月04日 07点09分
12
level 13
WarrnaCute
楼主
限制一条链首先需要限制目前已走过的点不乱跑以及链头每次扩展的点都是新点即可，目前走过的点不乱跑很好做到，我们给自己流自己的边给一个很小的费用，链头迫于流量的限制不得不往外扩张，而如果扩张了旧点就意味着边的流量消耗了而点的流量没有消耗，这么做的后果是点无法满流，所以他一定不会扩张旧点
2023年09月04日 08点09分
13
level 13
level 13
WarrnaCute
楼主
大家都知道费用流是NP的，那是因为时间复杂度和流量挂钩，但是我的费用流流量和n是一个量级，如果整个图是一个边双那么我的点数和边数是同级的都是nm的，于是我们就以n^3m^2的多项式时间复杂度内解决了单源哈密顿路径问题，而哈密顿通路只需要枚一下起点就可以做了，至此我们成功给出了著名NPC问题哈密顿通路问题的多项式时间复杂度解法，证明了P=NP，我已经准备好领取图灵奖了![[太开心]](/static/emoticons/u592au5f00u5fc3.png)
2023年09月04日 08点09分
15