“3 色问题的 NP-Complete 证明”

3 色问题 (3-Color) 的描述如下:给定一个图 G ,为 G 中每一个顶点涂色,要求每两个相邻的顶点颜色不一致。问是否可以用 3 种颜色完成上面的要求。 首先我们证明这个问题是 NP 问题。显然,若给定一个解,我们只需要遍历每一个节点,检查其与其相临节点的颜色是否一致,即可判断解是否正确。这个操作显然是可以在多项式时间内完成的,所以 3 色问题是 NP 问题。 接下来我们通过将 SAT 转换到 3 色问题来证明 3 色问题是 NP 难问题。即任意给定一个 SAT ,我可以…

“顶点覆盖问题 NP-Complete 证明”

顶点覆盖问题(Vertex Cover)的描述如下:给定 % <![CDATA[ <G,k> %]]> ,其中 G 是一个无向图,问图中是否存在点集 V % <![CDATA[ \lvert V \rvert <= k %]]> , 使得 V 中的每一个顶点覆盖 G 中所有的边。即 G 中每一条边的起点或终点都为 V 中的一个点。以下图为例, % <![CDATA[ <A,B> %]]> 就是一个符合条件的点集,因为图中的 4 条边,每一条边都连接了 % <![CDATA[ <A,B> %]]> 中至少一个点。 为了证明其 NP 完全,我们首先还是证明其是 NP 问题。给定一个 G 和一个 V ,我们只需要遍历 G 中的每一个边,检查其是否与 V 中一个点相连,即可判定 V 的正确性。显然这…

“分团问题 NP-Complete 证明”

分团问题(Clique Problem) 的描述如下:给定 % <![CDATA[ <G, k> %]]> ,其中 G 是一个无向图,问图中是否存在点集 V 组成一个团,且 % <![CDATA[ \lvert V \rvert <= k %]]> 。即 V 中的点相互连接?以下图为例。 % <![CDATA[ <B,C,D,E> %]]> 就是符合条件的一个点集,因为这四个点相互连接,即可以构成一个团。 首先我们为了真证明其 NP 完全,我们还是要先证明其是一个 NP 问题。若给定一个点集 V ,其中 % <![CDATA[ \lvert V \rvert <= k %]]> 。那么我只需要检查每一个 V 中的点是否与其他点相连,即可验证 V 的正确性。显然该验证步骤是可以在多项式时间内完成的,所以分

“3-SAT NP-Complete 证明”

阅读本篇需要先理解 SAT 问题是 NP 完全的,其主要由 Cook–Levin theorem 证明。有很多非常优秀的资源都对 SAT 的 NP 完全性作了证明,但这里就先省略掉了,还请读者自己参考。以后有时间的话我会补一个我理解的 SAT 证明问题。 3-SAT (3-CNF-SAT)的描述为:判断是否存在一个布尔表达式 C = C_1 \cap C_2 \cap \cdots \cap C_n ,其中 C_i = x_a \cup x_b \cup x_c ,使得 C = 1 。即判断是否存在布尔表达式 C = (x_a^1 \cup x_b^1 \cup x_c^1) \cap (x_a^2 \cup x_b^2 \cup x_c^2) \cap \cdots \cap (x_a^n \cup x_b^n \cup x_c^n) 为真。 为了证明 3-SAT 的 NP 完全性,我们需要 1) 证明它是 NP 问题。 2)证明它 NP 难(NP-Hard)。 3-SAT 与…

L_u 问题不可判定性的证明”

L_d 归约到 L_u

现在我们已经知道了 L_d 问题是不可判定的了,那么我们应该如何使用类似 L_d 这样的我们已经知道是不可判定了的问题呢?答案是:我们通过他们来证明更多问题的不可判定性。在这个过程中我们要使用一种叫做归约 (Reduce) 的方法。 规约简单的说,就是一个偷懒的过程,一个化简问题的过程。例如你已经知道了如何计算一个圆的面积,那如何来计算两个圆的面积呢?答案是将「计算两个圆的面积」这个我们未知的、高难度的问题化简到「做两…

“证明 L_d 的不可判定性”

图灵机的可判定性问题

L_d 问题是一个非常基本的不可判定问题,我们可以非常方便得将 L_d 问题规约到其他问题来证明其他问题的不可判定性。 L_d 的一般数学表达为:给定一个语言 L_d 满足: L_d=\{w_i \mid w_i \in L(TM_i)\} 判断 L_d 是否可决定 (decidable)。 w_i TM_i 分别指第 i 个字符串和第 i 个图灵机。换一句话说,判定一个图灵机是否可以停机接受它自己的编码。 为了证明 L_d 的不可判定性,我们这样思考: 我们假设 L_d 是可判定的,由于 L_d 一定是一个定义在 \{0, 1\} 上的语言,所以 L_d 一定是也是某一个图灵机的…

“矩阵求导”

分母布局

矩阵求导(Matrix Derivative)也称作矩阵微分(Matrix Differential),在机器学习、图像处理、最优化等领域的公式推导中经常用到。矩阵求导实际上是多元变量的微积分问题,只是应用在矩阵空间上而已,即为标量求导的一个推广,他的定义为将自变量中的每一个数与因变量中的每一个数求导。 具体地,假设存在 A_{m \times n} B_{p \times q} ,则 \frac{\partial A}{\partial B} 会将 A 中的每一个值对 B 中的每一个值求导,最后一共会得到 m \times n \times p \times q 个导数值。这么多的导数值,最后是排布成一个 m \times (n \times p \times q) 的矩阵…

“图片水印果然还是不适合我”

可能有观众已经发现了(虽然我觉得这个博客没有其他人关注),Soptlog (也就是你正在看的这个博客) 在上一个版本中所有文章中的图片左下角都有一个水印。而在这个版本所有的水印又都被去除了。起初加水印的动机很简单,一是为了测试一下 Ruby 调用 Nodejs 的能力,二是我发现有个博客在复制粘贴我的内容,还没有申明来源,所以就想用水印的方式来「显示主权」。现在看来还是不适合我。 实现方式 考虑到以后可能有小伙伴想要实现相似的功能,我还是简单简述…

“最近我在玩什么”

由于疫情的原因,这几个月虽然都是在家里上的课,但却感觉丝毫没有轻松下来。归根结底还是玩的太多了,于是反正技术向也没什么可写的,就写写我在玩些什么吧。 游戏 游戏的话说实话我这段时间玩的不多,原因是因为也没什么好玩的。马上次世代主机也要来了,索尼目前来看好像准备不是很充分的样子。从次世代主机的角度来说,好像被微软杀了个下马威嗷,现在都还没有公布外观细节,硬件方面给我的体会也只有 「 SSD 很快 」。另一方面,从这段…

“简易自动求导机”

利用二叉树实现简单的自动求导

很久很久以前,当计算机还不普及的时候,对一个复杂函数的求导一定是众多学者的噩梦之一。试想,也许面对一个三元多项式函数时,你还可以游刃有余地对每一个变量求导数,但当函数被拓展到成千上万元、成千上万项的时候,你还有信心求的出来导吗?于是,随着计算机的普及,自动求导算法的提出帮助众多学者从大型函数的求导中解放了出来。 深度学习的反向传播也是一个典型的自动求导过程,而作为 pytorch 魔法力量的核心 Autograd,一定也被很多人好奇…