创新实训个人记录：P versus NP

创新实训个人记录：P versus NP

• • computation&&computable&& computational efficiency
  • 一些符号
  • decision problem / language(决策问题)
  • 复杂性类别：P versus NP, NP-hard, NP-complete
  • • P
    • NP
    • NP-hard, NP-complete（NP难，NP完全）

computation&&computable&& computational efficiency

computation: 计算。以有限的步骤，从一组输入得到一个输出的过程；可以在各种物理和数学系统中进行，例如图灵机，λ演算，元胞自动机；所有这些形式的计算都是等效的，即每个模型都能够实现我们可以在任何其他模型上构想的所有计算
computable: 可计算的。不可计算的：对于某些输入，没有进入无限循环（即，永不停止）没有电脑能解决这些问题。
quantify computational efficiency: 量化计算效率。
举一个例子：两数乘法。第一种是重复添加，计算a·b,只需要把a加上它自己b-1次。另一种方法是下图所示的grade-school 算法。

我们通过学习，当我们增加输入的大小时，基本操作规模的数量是怎么样的，来量化一个算法的效率。我们设置，基本操作为一位的加法和乘法。（在其他设置中，我们也可以把除法设置为基本操作。）
输入的大小是数字中占位的数量。用于两个n位数乘法的基本操作的数量（即在$10^n-1$ 和 $10^n$之间的数字），用grade-school算法最多需要$2n^2$次（$n^2$次乘法，$n^2$次加法），用“重复加”算法至少需要$n10^{n-1}$次（a需要重复加自己b-1次，b是n位数，那么b是在$10^{n-1}$ 和 $10^n$之间的数字；通常，b-1≥$10^{n-1}$；又因为a是n位数，所以至少需要重复加$n10^{n-1}$次）。
可以看出，$2n^2$和$n10^{n-1}$根本不是一个量级的，效率高低也很明显。这就是计算效率，它很重要，这本书也主要是围绕计算效率来讨论。

一些符号

• 如果$S$是一个有限集合，那么在$S$上的字符串是一个$S$中元素的有限有序元组，元组元素来自于$S$。在这本书中，我们通常考虑在二进制{$0,1$}上的字符串。
• 对于任何非负整数$n$，我们用$S^n$表示在$S$上长度为$n$的字符串的集合（$S^0$表示由空元组组成的单例）。我们用$S^{\ast }$表示所有字符串的集合（即$S^{\ast }={\cup }_{n\ge 0}{S}^n$，$S^{\ast }$是所有$S^n$的并）。
• 那么，{0, 1}${}^n$就是表示在{0, 1}上长度为$n$的有限有序元组的集合，其中元组元素来自于{0, 1}。
• 如果$x$和$y$是字符串，那么我们用$x◦y$或者简单一点，用$xy$来表示$x$和$y$的联级（首先包含$x$的元素，然后是$y$的元素的元组）。如果$x$是一个字符串，而且$k\ge 1$是一个自然数，那么$x^k$表示$x$的$k$次复制的联级。例如，$1^k$表示一个包含$k$个$1$的字符串。字符串$x$的长度用$|x|$表示。

decision problem / language(决策问题)

由于技术上的方便，本书重点考虑决策问题。什么是决策问题？
举一个例子：The dinner party task（晚餐任务）。给定一个熟人清单，和他们之间不相处的对，找到你能邀请来聚会的最大熟人集合，保证每两个被邀请者都能和另一个相处。
为了解决这个问题，我们把它放到图里考虑。通过用图的顶点表示可能的参加晚宴的被邀请者，该图的顶点在任何两个不相处的人之间都具有边，则从介绍开始的晚宴计算问题就变成了寻找最大尺寸的独立集（一组顶点）的问题。
$INDSET=<G,k>:\exists S\subseteq V(G)s.t.|S|\ge kand\forall u,v\in S,\overline{uv}\notin E(G)$
输入INDSET，是否存在size≥k的独立集，这是一个布尔问题，输出只有一个位，0或1。

通过这个例子，我们可以知道决策问题大概是怎么样的了。输入一个问题，问题的答案只有“是”或“否”。用数学符号表示：如果机器计算函数$f_L$：{0，1}${}^{\ast }$→{0，1}，则机器会决定决策问题L⊆{0，1}${}^{\ast }$，其中$f_L（x）=1\iff x\in L$

复杂性类别：P versus NP, NP-hard, NP-complete

先介绍一个小概念：DTIME：Deterministic time，确定性时间。令T：N→N（N是自然数）为某种函数。 如果有一个图灵机在时间c·T(n)中运行某个常数c>0并确定L，那么我们称决策问题L在DTIME(T(n))中。我们讨论的图灵机更确切地来说是“确定性图灵机”。

P

然后呢，我们尝试使“高效计算”的概念更加精确。我们将其等同于多项式运行时间，这意味着对于某些常数c> 0，它最多为$n^c$。用数学符号表示：$P={\cup }_{c\ge 1}$ DTIME $(n^c)$. （P:polynomial）

两个需要注意的点：

• P类只包含决策问题。我们可以问“INDSET in P?" ; 但是对于两数乘法，我们不能问“整数乘法 in P?” ;而要问“整数乘法的决策版本 in P? ” ;用数学符号表示就是{<xy,i>: The ith bit of xy is equal to 1}
• 运行时间是输入位数的函数（二进制 位数）

NP

与P对比，先引出概念。P类包含可以有效解决的决策问题；NP类包含可有效验证其解决方案的问题集。

如果存在多项式$p：N\to N$和多项式时间TM $M$（称为决策问题L的检验器）使得对于所有$x\in${0, 1}${}^{\ast }$，有$x\in L$⇔$\exists u\in${0, 1}${}^{p(|x|)}$ $s.t.M(x,u)=1$ 则决策问题L⊆ {0, 1}${}^{\ast }$在NP中。($u$是对于$x$的certificate)
举个例子：对于线性规划$a_1{u}_1$ + $a_2{u}_2$ +··+ $a_n{u}_n$≤$b$，确定是否有满足所有不等式的变量$u_1$，…，$u_n$有理数的赋值。certificate是赋值。

$P\subseteq NP$：显然，因为多项式$p(|x|)$允许为0（换句话说，$u$可以是一个空字符串），所以$P\subseteq NP$。

NP-hard, NP-complete（NP难，NP完全）

如果可以在多项式时间内将所有NP问题归约为问题X，则认为X是NP-Completeness；
如果可以在多项式时间内将所有NPC问题归约为问题Y，则认为Y是NP-Hard；
如果同时在NP和NPH中，则该问题是NPC的。

NPC问题代表了NP中最困难的问题。 如果任何NPC问题具有多项式时间算法，则NP中的所有问题都可以。 NP完全问题集通常用NP-C或NPC表示。

NP-Hard问题不一定是NP问题，也不一定是决策问题。满足所有NP问题可归约到NPC，所有NPC可归约到NPH。

总结

以上是生活随笔为你收集整理的创新实训个人记录：P versus NP的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。