NP问题

$NP$ $N P$ 表示“Non-Deterministic Polynomial”——“非确定的多项式”
- 解可以在多项式时间内验证
- 非确定的图灵机在多项式时间内可以解决
$P$ $P$ 表示“Polynomial”——“多项式”
- 是一个 $NP$ 问题
- 确定的图灵机在多项式时间内可以解决
“ $NPC$ $N P C$ ”表示“Non-Deterministic Polynomial Complete”——“非确定的多项式完全”
- 是一个 $NP$ 问题
- 任何NP问题都可以在多项式时间内规约到这个问题
“ $NPH$ $N P H$ ”表示“Non-Deterministic Polynomial Hard”——“非确定的多项式难”
- 解不能在多项式时间内验证
- 任何NP问题都可以在多项式时间内规约到这个问题

$P$ 问题和 $NP$ 问题的解都可以在多项式时间内验证

# 3CNF-SAT问题

给定 $n$ 个布尔变量 $x_1,x_2,x_3\dots x_n$ 和一个布尔表达式 $C$ ，形式为：

求使布尔表达式为真的布尔变量 $x_1,x_2,x_3\dots x_n$ 值。

显然，对于一组布尔变量 $x_1,x_2,x_3\dots x_n$ 值，依次求解每个子句的值，再求其析取的值即得最终的值，时间复杂度为 $O(n)$ ，是 $NP$ 问题。

“ $k$ 团”是指一种有 $k$ 个点的子图，子图中的点两两之间都有边相连。

$k$ 团问题就是给定一个图 $G$ 和整数 $k$ ，求 $G$ 的 $k$ 团。

显然，对于 $G$ 中的任意 $k$ 个顶点组合，只需要判断两两之间是否有边即可判断是否是 $k$ 团，时间复杂度 $O(n^2)$ ，是 $NP$ 问题。

汉密尔顿回路是指一条经过无向图中所有点且每个点只经过一次的路径。

汉密尔顿回路问题就是给定一个图 $G$ 寻找它的汉密尔顿回路。

显然，对于 $n$ 个顶点的排列，只需要依次判断顶点之间是否重复以及相邻顶点间是否有边即可验证是否是汉密尔顿回路，时间复杂度为 $O(n)$ ，是 $NP$ 问题。

一个最优化问题可以和一个判定问题对应起来：

$P$ 、 $NP$ 、 $NPC$ 可以如下表示：

$P$ $P$ 类最优化问题：
- 对应的判定问题可以在多项式时间内解决
- 对应的最优化问题可以在多项式时间内解决
$NP$ $N P$ 类最优化问题：
- 对应的判定问题可以在多项式时间内解决
- 对应的最优化问题不一定能在多项式时间内解决
$NPC$ $N P C$ 类最优化问题：
- 对应的判定问题可以在多项式时间内解决
- 对应的最优化问题不一定能在多项式时间内解决
- 所有的 $NP$ 问题都可以在多项式时间内归约到这个问题
$NPH$ $N P H$ 类最优化问题：
- 对应的判定问题不能在多项式时间内解决
- 所有的 $NP$ 问题都可以在多项式时间内归约到这个问题

目前是否有 $P=NP$ 还在探索之中，普遍认为 $P\not=NP$ 。

证明该问题是一个 $NP$ 问题：找出一个多项式时间内验证解的办法
将该问题规约到一个 $NPC$ 问题：找出一个多项式时间内将某个已知 $NPC$ 问题的解转化为该问题的解的办法，并证明当且仅当 $NPC$ 问题有解时该问题有解