归约小记

问题和计算能力

问题

我们定义为 $01$ 串到 $01$ 串的映射，在多项式意义下，可以定义为 $01$ 串到 $0/1$ 的映射，即所有问题都是判定问题。

后者也被称为语言，一个语言可以用一个集合 $S$ 表示，里面存储了所有被判定为 $1$ 的输入。

图灵机

程序是一个自动机，附有无限长的内存和一个指针。

输入是纸带的初始状态，输出是结束状态。

自动机的每个节点存储：若当前指针指向 $0/1$ ，则下一步向左/向右，当前指针的值变成什么，自动机走向哪个节点，以及是否停机。

显然一个图灵机可以用一个 $01$ 串编码。

带真随机数生成器的图灵机的计算能力与带无限内存的现代电子计算机的计算能力相当，显然我们可以把一个现代 cpp 程序进行一些不改变多项式性的改写。

对于时间复杂度的表示：我们所说的多项式是关于输入长度成多项式关系，而不是某个输入数值。

停机问题

图灵机的可用内存和自动机编号都是有限的，显然若某个图灵机两次到达相同的状态，那么此后它还会一直循环这个过程，也就是说图灵机是有可能无法停机的。

问题 1：给定图灵机 $T$ ，判断其是否存在一个输入使得它能停机，这个问题是否能用图灵机在有限时间内给出判断。

不存在。

证明：假设存在 $H(T)$ ，则我们构造 $H'(T)$ ：当 $H(T)$ 判断其停机时，死循环，否则停机。

则 $H'(H')$ 是不合形式逻辑的。

问题 2：给定图灵机 $T$ 和输入 $S$ ，判断 $T(S)$ 的运行是否能停机，这个问题是否能用图灵机在有限时间内给出判断。

不存在。

仍然假设存在 $H(T,S)$ 。

我们尝试套用刚刚的证明方法，但我们发现硬套的话，我们会得到 $H'(H',(H',\cdots)))$ 的无限嵌套，显然违背了程序的有限性。

考虑更巧妙的套用方法，定义 $H'(T)$ 表示若 $H(T,T)$ 判断停机，死循环，否则停机。

则 $H'(H')$ 是不合形式逻辑的。

归约

将 A 归约到 B 的意思是我们可以用 B 做 A，即 A 的计算难度弱于 B，计算难度的意义上，这是一个偏序关系。

为了方便，我们记作 A < B 或 B > A，即计算难度上的大于小于。

我们可以进行映射归约，即一个问题只能调用一次另一问题，也可以进行图灵归约，多项式次数内调用即可。

通常来说，归约时写明调用的次数即可。

指数归约

问题类：P/NP/NPC/NP-Hard

多项式复杂度可以解决的问题称作 $\mathbb P$ 问题。

多项式复杂度可以验证的判定问题称作 $\mathbb{NP}$ 问题。

若一个问题不弱于所有的 $\mathbb{NP}$ 问题，则我们称其为 $\mathbb{NP}\text{-Hard}$ 。

若一个 $\mathbb{NP}$ 问题不弱于所有的 $\mathbb{NP}$ 问题，则我们称其为 $\mathbb{NP}\text{-Complete}$ ，简称 $\mathbb {NPC}$ 。

解决了 $\mathbb {NPC}$ 问题就可以在多项式复杂度内解决所有的 $\mathbb{NP}$ 问题，从而证明 $\mathbb{P=NP}$ ，目前人类没有发现 $\mathbb{P=NP}$ 或 $\mathbb{P\ne NP}$ 的决定性证据。

常见 NPC：

SAT、最小覆盖问题/精确覆盖问题。
2-SAT 计数/最大化成立子句个数/最大化变量成立个数。
$w$ 子集和问题（ $w=0$ 的特例也是 NPC）、背包问题、装箱问题/多背包问题/多机调度问题。
一般图最大团/最大独立集、有向图/无向图最长简单路径、有向图/无向图哈密顿回路/路径、TSP、最大割。

下面说几个方便证明的，可以参考其中优秀的构造思路。

SAT is NPC

对图灵机的每个时刻进行编码压缩，不难发现图灵机的运算过程可以写成逻辑表达式，且我们可以故意留空一些输入。

SAT 的意思是判断逻辑表达式组是否有解。

如此，如果我们会 SAT 问题，且对于一个问题有一个多项式时间内的验证算法，我们对其进行 SAT 就可以得到一个多项式的判定算法，即 $\mathbb{P=NP}$ 。

3-SAT = SAT

这里的等号其实不严谨，但我们可以说明每个规模为 $n$ 的 SAT 问题都能转化为规模为 $\mathcal O(n)$ 的 3-SAT 问题。

首先将 SAT 写成 $(x_1\vee x_2\vee\cdots\vee x_k)\wedge(\cdots)\wedge\cdots$ 的形式（每个 $x$ 都可能是 $x/\neg x$ ），然后考虑每个长式的表达式树，考虑新建几个变量来承载中间过程即可，现在我们只需描述 $x_1\vee x_2=x_3$ ，等号也是好描述的， $a=b\iff (a\wedge b)\vee(\neg a\wedge\neg b)$ 。

精确覆盖问题 is NPC

问题形式：给定 $n$ 个集合，值域为 $\Theta(n)$ ，判断是否能够选出一些子集恰好覆盖全集。

考虑归约 3-SAT，SAT 中的一个变量就是该问题中的一个集合。

可以构造变量的取反，直接在某一位只有他俩有值即可。

考虑直接构造每个子式的真值表，对于一个大小为 $3$ 的子式，一定有 $7$ 种取值是合法的，我们用 $4$ 位来承载该子式，对于涉及的三个变量我们分别在 $1,2,3$ 位设为 $1$ ，然后新增 $7$ 个额外集合，它们的第 $4$ 位都是 $1$ ，前三位是 $7$ 种合法取值的补集，这样就限制好了。

一般图最大团/最大独立集 is NPC

原图的最大团是补图的最大独立集，下文用最大独立集来说明，我们仍然归约 3-SAT。

令一个点为一个变量。

可以构造变量的取反，直接连一条边。

对于一个子式 $x_1\vee x_2\vee x_3$ ，我们构造一个新点 $y$ 连向 $x_1,x_2,x_3$ ，则若三者选至少一个可得 $y$ 不选，再次新建 $y$ 的反面 $u$ ，我们希望 $u$ 尽可能成立，所以重复 $k$ 次把 $u$ 的复制连向 $y$ 。

判断最大独立集是否等于 $km+n$ 即可， $m$ 为子句数， $n$ 为变量数。

哈密顿回路 is NPC

归约 3-SAT。

先来证明有向图版本。

考虑用两个点 $u,v$ 表示一个变量，从左走到右表示 $x=1$ ，从右走到左表示 $x=0$ ，考虑 $x_1\vee x_2\vee x_3$ ，只要三者任一成立，该限制就满足。

于是我们新增一个 $y$ 表示该子式， $u_{x_1}\to y\to v_{x_1}$ 就表示 $x_1=1$ 时可以”捎上“这个子式，若需要多次用到 $x_1$ ，我们就用一条长链表示 $x_1$ ，从左向右遍历这条链表示 $x=1$ ，从右向左表示 $x=0$ ，这样就有捎带多个子式的能力了。

问题：会不会有 $u_{x_1}\to y\to v_{x_2}$ 这种”串门“事件发生呢，你发现此时 $v_{x_1}$ 所有的入边（ $u,y$ ）都遍历过了，不可能存在哈密顿回路，同理一条链不可能从中间拐走不遍历完，就算从另一侧再次遍历也会因为”回路“的限制走不回去。

连边上，我们还要加上”链头、链尾向每个链头、链尾连双向边“。

无向图版本，考虑一个哈密顿回路的翻转仍然是哈密顿回路，所以如果要复刻有向图，关键在于头接尾、尾接头。

将一个点拆成入点、中点、出点，用无向边顺次连接，这样如果到了入点却不遍历中点和出点，那么中点即使又被出点访问也出不去了，构造完成。

同理，最长简单路和 tsp 显然可以用来判断哈密顿回路。

多项式归约

多项式归约的主要方向有：矩乘、 $(\min,+)$ 卷积、SETH 及其衍生物（OV）、3SUM/3XOR。

矩阵乘法

链 mex

mex 的二分版本可以做到查询是否有两个集合并起来为全集，规约 OV。

链颜色数

区间加减全局 0 的个数

改为加减 1

小 Z 的袜子

也就是区间相等对数。

可以归约到

区间逆序对

大于号算一遍，小于号算一遍，得到区间相等对，归约到小 Z 的袜子。

能否用区间相等对去做区间逆序对？

SETH 强指数时间假设

假设的内容：SAT 问题不存在多项式解法，且其指数解法的复杂度不低于 $2^n$ ，注意这里说的并不是 3-SAT 而是任意 SAT。

OV 的归约依赖于此。

OV > SETH

多项式归约，有两个主要的方向：01 矩阵乘法和 OV。

3SUM/3XOR

判断能否选出三个数的和/异或等于 $0$ 。

目前没有发现低于平方的做法，值域很小时有 FFT 做法（arc185_c）。

4SUM

3SUM < 4SUM，归约方法考虑足够大的量 $W$ ，是往集合中扔一个 $-3W$ ，并且原来的每个数加上 $W$ 。

4SUM 可以做到平方，把所有数对扔进哈希表即可。

行列斜线加（[NOI2023] 方格染色）

考虑无限拉长每条线，不平行的线一定相交，则询问全局和就可以得到三线共点的个数。

考虑代数意义、横线是 $y=a$ ，竖线是 $x=b$ ，斜线是 $y-x=c$ ，于是若有三线共点，则 $a-b=c,a=b+c$ ，归约 3SUM。