计算机算法理论复杂度分析：P和NP问题

P、NP、NP-hard 和 NP-complete 是计算复杂性理论中的关键概念，用于描述不同类型的计算问题以及它们的求解难度。

P 类问题

P 类问题是指多项式时间内可以通过确定性算法解决的问题。这意味着，给定一个输入，问题可以在有限的步骤内得到解决，且步骤的数量是输入大小的多项式函数。换句话说，P 类问题的求解效率较高。例如，最短路径问题和排序问题都是 P 类问题。

NP 类问题

NP（Non-deterministic Polynomial time）类问题是指能够在多项式时间内验证解是否正确的问题。换句话说，虽然找到问题的解可能比较难，但一旦给出了解，我们可以在多项式时间内验证它是否正确。一个典型的 NP 问题是旅行商问题：找出某个城市之间的最短旅行路径可能很复杂，但给定一条路径，我们可以快速验证它是否满足要求。

NP-complete 问题

NP-complete 问题是 NP 类问题中的一种特殊类型。这类问题满足以下两个条件：

• 它是 NP 类问题，意味着给定解后可以在多项式时间内验证其正确性。
• 它是 NP 类问题中最难的问题，也就是说，如果我们能够找到某个 NP-complete 问题的多项式时间求解算法，那么所有 NP 问题都可以通过多项式时间内解决。

经典的 NP-complete 问题包括布尔可满足性问题（SAT）和哈密顿路径问题。

NP-hard 问题

NP-hard 问题是比 NP 类问题更难的一类问题。这类问题不一定属于 NP 类，即它们的解不一定能够在多项式时间内验证。例如，NP-hard 问题可以是一些更为广泛的问题（如优化问题），或者一些根本无法在多项式时间内验证解的准确性的问题。如果一个 NP-hard 问题有多项式时间的解法，那么所有 NP 问题都可以在多项式时间内解决。

P = NP 问题

计算机科学中最大的未解问题之一是P 是否等于 NP。如果 P = NP，那就意味着所有 NP 类问题实际上都可以在多项式时间内解决。然而，目前还没有证明这个命题是否成立。

O(N!)/O(2^N)算法是P还是NP？

如果一个算法的时间复杂度是 O(N!) 或 O(2^N)，它不属于 P（多项式时间）算法。以下是原因：

P（多项式时间）P 类问题可以在多项式时间内解决，即它们的时间复杂度是输入规模的某个多项式函数，例如 O(N)、O(N^2) 等。与非多项式函数相比，这些增长相对较慢。

O(N!)（阶乘时间）和 O(2^N)（指数时间）的增长速度远远快于任何多项式函数。O(N!) 增长非常快，其中 N! 是 N 的阶乘。

O(2^N) 是指数增长，随着 N 的增加，它也会变得不可计算。

由于这些复杂度比任何多项式函数的增长速度要快得多，具有这些时间复杂度的算法不属于 P 类。

它是 NP 吗？

要判断这样的算法是否属于 NP，重要的是要理解 NP 并不指问题的求解时间，而是指一旦给出解后，验证解是否正确的时间。

如果某个问题的时间复杂度为 O(N!) 或 O(2^N)，它可能属于 NP，也可能不属于，这取决于给出解后能否在多项式时间内验证。如果可以在多项式时间内验证解，那么这个问题可能属于 NP 类，尽管求解非常困难。

O(N!) 或 O(2^N) 不属于 P 类，因为求解该问题所需的时间增长速度太快，无法视为“高效”。

它是否属于 NP 取决于解能否在多项式时间内验证。如果验证过程是多项式时间的，那么该问题属于 NP 类，但并不是所有 O(N!) 或 O(2^N) 问题都在 NP 中。

总结

• P 类问题：可以在多项式时间内求解的问题。
• NP 类问题：解可以在多项式时间内验证的问题。
• NP-complete 问题：最难的 NP 问题，能够解决它就能解决所有 NP 问题。
• NP-hard 问题：不一定属于 NP 类，但至少和 NP-complete 问题一样难。

这个分类系统帮助我们理解各种问题的计算复杂性以及它们之间的关系。

英文：P versus NP problem (NP Complete, NP Hard)

相关文章：

1. 按揭贷款(房贷,车贷) 每月还贷计算器 去年给银行借了17万英镑 买了20万7500英镑的房子, 25年还清. 前2年是定率 Fix Rate 的合同 (年利率2.49%). 每个月大概是还 700多英镑. 有很多种还贷的计算方式, 定率/每月固定 是比较常用的. 简单来说就是 每个月交的钱是...
2. 智能手机 HTC One M9 使用测评 虽然我对手机要求不高, 远远没有像追求VPS服务器一样, 但是怎么算来两年内换了四个手机, 先是三星 S4 用了一年多, 然后 Nokia Lumia 635 Windows Phone, 后来又是 BLU, 半年多前换了...
3. SteemIt 高级定制微信文章列表 RSS/API/阅读器 v2.0 The Advanced Wechat Group Posts Feed/API/Reader v2.0 Abstract: I have added five parameters to the...
4. 同一台服务器上多个WORDPRESS站点的一些设置可以移出去 我自从把所有网站都挪到一处VPS服务器上 就发现很多事情省事很多 可以同时管理多个网站 包括 WORDPRESS博客. 比如我有四个WORDPRESS博客 然后我就把通用的一些资料给移出去 移到 HTTP或者HTTPS都不能直接访问的文件夹里这样就更安全许多. 文件 wp-conn.php 存储了 相同的数据库资料. 1 2...
5. 在英国带孩子去露营全攻略 之前就做了一些露营的准备工作, 因为大儿子Eric 很兴奋说是要去 Camping Holiday 估计是在 Papa Pig 里看到的. 英国有很多可以露营的地方, 最后面选了一个离家开车1个多小时. 看了评论还不错. 地址为: New Road,...
6. 在英国开车的简单介绍/英国开车上路需要准备什么? 在英国合法上路需要有: 有效的驾照; MOT 车的年检; 路税 (Road Tax);还有最重要的汽车保险; 四者缺一不可. 千万不要有侥幸心理, 因为警察现在都高科技, 都能扫描车牌就能知道你合不合法. 不合法直接拦下来轻则罚款, 重则扣车上述法庭. 驾照 在英国可以用欧盟的大部分驾照,...
7. LOGO 海龟作画 系列三 递归画一个国际象棋棋盘 今天我们要来讲一讲递归. 递归就是函数自己调用自己, 我们可以定义一个过程, 然后这只海龟不停的画, 结束的时候再调用自身再继续画. 再次调用的时候参数变化了, 至到参数满足一定的条件则停止. 比如 下面定义的这个过程可以用来画一个实现的正方形. TO FK :B IF :B>15 ;...
8. 老婆的配偶签证被拒 郁闷死了, 601镑签证费打水漂,一去不回!费钱费力. 去年12月份我请了律师拿到了永居.老婆是T1G签证的陪工签 (DEPENDENT VISA) 2016年4月份到期. 然后我就想说得趁早把她的签证转成配偶签(SPOUSE)这样她就可以尽快走五年永居的路线. 今天收到拒签信,原因是我没有提供 有工资进帐的那份银行帐单,我提供了我和我老婆的联名帐户, 但是工资并不是直接打到这个帐单上的.所以就这一点被拒了.完全不给解释,不给补材料的机会.601镑就这样再见了. 英国的签证寄出之后是先由另一个部门先收费, 收完费才正式审理,而且不管结果如何是不退钱的.后悔没让律师弄,也不至于到现在浪费这么多时间和金钱,签证还没过.由于原签证还没到期,所以还不能上述.估计只能等搬完家后年底请律师搞定这事. 真是郁闷, 600镑, 我可以再买一个IPHONE6,或者给我的新买的车换四个轮胎....