什么是P问题、NP问题和NPC问题

时间：2018-07-19 22:27人气：来源：网络整理

原文中有几处不是很理解，望赐教。
1. “现在某人拿到了一个求最短路径的问题，问从起点到终点是否有一条小于100个单位长度的路线。它根据数据画好了图，但怎么也算不出来，于是来问我：你看怎么选条路走得最少？我说，我RP很好，肯定能随便给你指条很短的路出来。”。那如果这个问题本身就没有小于100的路线，自然也就选不出来，那样岂不就不是NP问题了？
2.“但我要把问题换成这样：试问一个图中是否不存在Hamilton回路。这样问题就没法在多项式的时间里进行验证了，因为除非你试过所有的路，否则你不敢断定它“没有Hamilton回路”。”在这个问题中，我也可以假设我的RP非常好，一下子找到了一条Hamilton回路并验证了它，那这样问题岂不迎刃而解了？因为“图中存在一条Hamilton回路”。

2013年2月26日 14:40 /