TOC中的P类和NP类是什么？

  • Z时代
  • 2024-01-10
  • 分类：综合

首先，让我们了解计算理论(TOC)中的 P 类。

P级

  • P 类由可在多项式时间内解决的问题组成，即这些问题可以O(n k)在最坏的情况下及时解决，其中 k 是常数。

  • 这些类型的问题称为易处理的，而其他类型的问题称为难处理的或超多项式。

  • 通常，一个算法是多项式时间算法，如果存在多项式p(n)使得该算法可以在 O( p(n))时间内解决任何大小为 n 的实例。

  • 需要 Ω(n 50) 时间来解决的问题对于大 n 来说本质上是难以处理的。大多数已知的多项式时间算法在时间 O(n^k) 内运行，k 值相当低。

  • 多项式时间算法类的优点是所有合理的确定性单处理器计算模型都可以相互模拟，最多使用多项式慢-d。

NP级

  • NP 类由多项式时间可验证的问题组成。NP 是一类决策问题，借助一些额外信息，很容易检查给定答案的正确性。因此，我们不是在寻求找到解决方案的方法，而只是为了验证解决方案确实是正确的。

  • 给定类别中的每个问题都可以使用穷举搜索在指数时间内解决。

例子

考虑一个例子来检查问题是属于 P 类还是 NP 类

Step 1 - 如果问题属于 P 类，那么我们可以在多项式时间内找到该类型问题的解决方案。

步骤 2 - 如果问题属于 NP 类，那么我们只能在多项式时间内验证可能的解决方案。

步骤 3 - 考虑另一种方式，NP 意味着问题是非确定性多项式的。具体来说，这意味着如果您可以构建一台能够同时尝试所有可能解决方案的机器，它可以在多项式时间内完成。

我们知道这是真的，因为我们知道我们可以在多项式时间内验证一个可能的解决方案，而这台机器所做的基本上是尝试同时验证（测试）问题的所有潜在答案。

Step 4 - 所以，如果你能在多项式时间内解决一个问题，你当然可以在多项式时间内验证你的答案是正确的，不是吗？当然，如果你能证明你的算法是正确的，并且它可以在多项式时间内找到答案，那么它必须在 P 中。

以上是 TOC中的P类和NP类是什么？ 的全部内容， 来源链接： utcz.com/z/341386.html

回到顶部