N、NP、NPC问题分析

2023-12-02 08:54:34

O(1), O(logn),O(nlogn),O(n),O(n^2)或者o(nk)等为多项式：ax^n-bx(n-1)+c

Polynomial（多项式复杂度问题）

对于一个问题，假如现在某个解，如果能在多项式时间内验证这个解是否为正确解，那么这个问题就是NP问题。
例子：
假设有一个没有重复元素的数组arr ＝［…］，现在我们希望找到它的中位数median

NP complete问题是NP问题的一个子集。

假如一个问题是NP问题，也就是说能在多项式时间内进行判断，但是暂时没办法在P时间内解决，那么这个问题就是NP complete问题。

本质相同，问题可以互相转换（多项式时间内）

一个是Ｐ，其它都是Ｐ
例子：
Clique（两点之间互相连接ei）

Clique Problem 和 3-SAT
clique problem：在图中找全连接

每个点不相连

点覆盖所有的线条

线条包含所有的点

对问题施加限制
改进指数时间算法（2^n -> 1.5^n）
启发示方法

回溯法（是一种选优搜索法，又称为试探法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为“回溯法”，而满足回溯条件的某个状态的点称为“回溯点”）
局部搜索（局部搜索算法从一个初始解开始，通过邻域动作，产生其邻居解，判断邻居解的质量，根据某种策略，来选择邻居解，重复上述过程，至到达终止条件，容易陷入局部最优）
- 随机游动
- 模拟退火（为了防止陷入局部最优，模拟退火算法以一定概率接受比当前解差的解，接受差解的概率随着迭代次数的增加而下降，或者说是随着温度T的下降而下降）
  遗传算法（模拟物竞天择的生物进化过程，通过维护一个潜在解的群体执行了多方向的搜索，并支持这些方向上的信息构成和交换）

P Problem: 对于任意的输入规模n，问题都可以在n的多项式时间内得到解决
NP(Non-deterministic Polynomial) Problem: 可以在多项式的时间里验证一个解的问题
NPC(Non-deterministic Polynomial Complete) Problem: 满足两个条件 (1)是一个NP问题 (2)所有的NP问题都可以约化到它
NP-Hard Problem: 满足NPC问题的第二条，但不一定要满足第一条