数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律研究计算理论 (TOC) 中的 P 类和 NP 类是什么？
首先，让我们了解计算理论 (TOC) 中的 P 类。
P 类
P 类包含那些可以在多项式时间内解决的问题，即这些问题可以在最坏情况下以 O(nk) 的时间解决，其中 k 是常数。
这类问题称为易处理问题，其他问题称为难处理问题或超多项式问题。
通常，如果存在一个多项式 p(n)，使得算法可以在 O(p(n)) 的时间内解决任何大小为 n 的实例，则该算法是多项式时间算法。
需要 Ω(n50) 时间才能解决的问题对于较大的 n 本质上是难处理的。大多数已知的多项式时间算法在 O(nk) 时间内运行，其中 k 的值相当低。
多项式时间算法的优势在于，所有合理的确定性单处理器计算模型最多都可以以多项式慢速模拟彼此。
NP 类
NP 类包含那些可以在多项式时间内验证的问题。NP 是一类判定问题，借助少量额外信息，很容易检查给定答案的正确性。因此，我们不是要求寻找解决方案的方法，而只是要求验证解决方案确实是正确的。
该类中的每个问题都可以使用穷举搜索在指数时间内解决。
示例
考虑一个示例，以检查问题属于 P 类还是 NP 类
步骤 1 - 如果一个问题属于 P 类，则意味着我们可以在多项式时间内找到该类型问题的解决方案。
步骤 2 - 如果一个问题属于 NP 类，则意味着我们可以在多项式时间内验证可能的解决方案。
步骤 3 - 考虑另一种方法，NP 表示非确定性多项式。具体来说，这意味着如果您能够构建一台能够同时尝试问题所有可能解决方案的机器，它可以在多项式时间内完成。
我们知道这是正确的，因为我们知道我们可以在多项式时间内验证可能的解决方案，而该机器基本上是在同时尝试验证（测试）问题的潜在答案。
步骤 4 - 因此，如果您可以在多项式时间内解决问题，您当然可以在多项式时间内验证答案的正确性，不是吗？当然，如果您能够证明您的算法是正确的，并且它可以在多项式时间内找到答案，那么它必须属于 P 类。
18K+ 次浏览
