经过一些阅读,我感到很困惑:
P在NP中,而NP在NP-Complete中。那么所有的P都可能在NP和NP-Complete中吗?
这是否意味着有可能存在既是NP又是NP-Complete的排序算法?
希望这不会听起来太蠢。
经过一些阅读,我感到很困惑:
P在NP中,而NP在NP-Complete中。那么所有的P都可能在NP和NP-Complete中吗?
这是否意味着有可能存在既是NP又是NP-Complete的排序算法?
希望这不会听起来太蠢。
首先:
P在NP中;NP在NP-Complete中。因此,所有的P都可能在NP和NP-Complete中?
这是一个相当重要的声明,因为你所说的意味着 P=NP。目前还没有人能够证明或否定它。因此,事情的现状如下:
排序数字
给定一个数字列表,您可以在多项式时间内验证该列表是否已排序,因此该问题显然是 NP。
已知有算法可以在多项式时间内对数字列表进行排序(例如冒泡排序O(n ^ 2)等)。 因此,该问题是 P 。
希望这可以帮助您。
考虑阅读此博客。
P、NP、NP-hard和NP-complete是问题的复杂度类;它们描述的是一个问题,而不是算法。