什么是NP问题?
0 681
0
该提问暂无详细描述
收藏
2021-02-14 09:39 更新 空心人 •  3374
共 1 个回答
高赞 时间
0

NP问题

NP问题是非确定性多项式问题,是指算法无法直接计算出结果,只能通过进行一些有选择的“猜算“来得到结果。

非确定性多项式问题

对于这类问题给出的算法并不能直接计算出结果,但可以检验某个可能的结果是正确的还是错误的。这个可以检验“猜算“的答案正确与否的算法,如果可以在多项式时间内解出,就是非确定性多项式问题。 例如,查找一个很大的质数的数学问题,目前所知并不存在一个确定的公式可以用来推算并找到这个很大的质数。但是,如果实现给定一个数,程序可以在多项式时间内判断出它是否满足要求。

NP-完全问题

NP问题一直是计算机科学领域理论研究者研究的热门话题。在NP问题中,存在一个叫做“NP-完全问题“的子集,也是最难的NP问题。由于所有的NP问题都可以多项式归约为NP-完全问题,因此,目前关于NP问题的研究主要集中在NP-完全问题的研究上,较为典型的有装箱问题、背包问题、着色问题等。

NP问题的研究结果

NP问题的研究结果有两种可能:一种是找到了求解问题的算法,一种是求解问题的算法是不存在的,那么就要从数学理论上证明它为什么不存在。

收藏
2021-02-14 09:42 更新 小眼的铁板烧 •  3526