NP 类代表非确定性多项式时间,是计算复杂性理论的核心,包含具有多项式时间验证器的决策问题。 决策问题是需要是或否答案的问题,在这种情况下,验证器是一种检查给定解决方案正确性的算法。
区分解决问题(计算)和验证解决方案(验证)非常重要。在 NP 中,重点在于是否存在可以确认解决方案正确性的多项式时间验证器。
P 类代表多项式时间,包括可由确定性图灵机在多项式时间内解决的决策问题。 因此,对于 P 中的每个问题,不仅有一个多项式时间算法来找到解决方案,而且还有一个多项式时间算法来验证一个解决方案。
表面上的矛盾在于观察到 P 中的每个问题本质上具有多项式时间求解算法,也具有多项式时间验证器。 然而,这并不与NP的定义相矛盾。 NP 的定义特征是存在多项式时间验证器,无论找到解决方案可能需要多长时间。 这意味着 P 中的所有问题也是 NP 中的,因为它们的解决方案可以在多项式时间内验证。
例如,考虑素数测试的问题。 这个问题可以用两种方式来描述:生成素数和验证给定数是否是素数。 埃拉托色尼筛法是一种生成一定限度内的所有素数的算法,并且效率很高,但其时间复杂度不是计算复杂度理论中严格意义上的多项式; 它通常表示为 O(n log log n),这比线性更好,但根据 P 的定义不是严格的多项式。另一方面,验证给定数字是否为素数(素数测试)的问题是不同的任务。 AKS 素数测试等高效算法允许在多项式时间内进行素数验证。 因此,在验证的背景下,素数测试问题属于 P 类,也属于 NP 类,因为一个解(一个数是否是素数)可以在多项式时间内验证。 这表明,虽然素数生成和素数测试相关,但它们在计算复杂性方面涉及不同的考虑。
总之,NP 具有多项式时间验证器的定义与 P 的性质一致。区别不在于验证步骤,而在于寻找解决方案的过程:P 问题在多项式时间内可解决和可验证,而 NP 问题可以在多项式时间内验证,但并不总是知道它们是否可以在多项式时间内求解。
最近的其他问题和解答 复杂:
- PSPACE 类不等于 EXPSPACE 类吗?
- P 复杂性类别是 PSPACE 类别的子集吗?
- 我们能否通过在确定性 TM 上为任何 NP 完全问题找到有效的多项式解来证明 Np 和 P 类是相同的?
- NP 类可以等于 EXPTIME 类吗?
- PSPACE 中是否存在没有已知 NP 算法的问题?
- SAT 问题可以是 NP 完全问题吗?
- 如果存在可以在多项式时间内解决问题的非确定性图灵机,那么问题是否可以属于 NP 复杂性类别
- NP 是具有多项式时间验证器的语言类别
- P 和 NP 实际上是相同的复杂度类别吗?
- P 复杂性类别中的每种上下文无关语言都是如此吗?
更多问题及解答:
- 领域: 网络安全
- 程序: EITC/IS/CCTF 计算复杂性理论基础 (前往认证计划)
- 教训: 复杂 (去相关课程)
- 主题: NP的定义和多项式可验证性 (转到相关主题)