SAT分半到正交向量 | Codeboy's Blog

形式陈述

本页的双色正交向量问题（OV）输入两个有索引的列表 $A,B$ ，每个列表至多含 $N$ 个 $d$ 维 $0$ – $1$ 向量，问是否存在一对 $a\in A,b\in B$ 满足

a\cdot b=\sum_{j=1}^d a[j]b[j]=0.

点积在普通整数上计算，不是模2内积。列表允许重复向量，每个条目仍保留独立索引。穷举所有跨列表的向量对可在 $O(N^2(d+1))$ 时间内求解，这一写法也涵盖零维情形。

设 $F=C_1\land\cdots\land C_m$ 是含 $n$ 个变量的CNF。把变量分为大小 $\lfloor n/2\rfloor$ 与 $\lceil n/2\rceil$ 的两部分，可构造

|A|=2^{\lfloor n/2\rfloor},\qquad |B|=2^{\lceil n/2\rceil},\qquad d=m,

并满足

F\text{可满足}\quad\Longleftrightarrow\quad \exists a\in A,\ b\in B:\ a\cdot b=0.

若存在某个固定 $0<\varepsilon\le1$ ，使所有 $N,d$ 上的OV都能由确定性算法在 $O(N^{2-\varepsilon}\operatorname{poly}(d))$ 时间内解决，则每个固定 $k$ 的 $k$ -SAT都有 $O^*(2^{(1-\varepsilon/2)n})$ 时间算法。这与本库确定性版本的SETH冲突。下面给出构造、双向正确性、完整小例，以及每一项规模费用。

直觉

一个部分赋值不能单独判断整条子句最终是真是假，但能判断“我这一半是否已经找到一个真的文字”。若左半已经满足子句，右半可以任意；若左半尚未满足，右半必须负责满足。把“已经满足”记为0、“尚未满足”记为1，两边都失败时才会在对应坐标产生乘积1。

因此点积不仅检测是否有冲突，还精确数出拼接赋值违反了多少条子句。先分别列出两半赋值，将原来的 $2^n$ 对组合变成两个各约 $2^{n/2}$ 的列表；困难集中到能否显著快于二次时间找到一对兼容向量。

每个坐标的语义与双向证明

记两半变量集为 $V_L,V_R$ 。对每个左侧赋值 $\alpha:V_L\to\{0,1\}$ 定义

a_\alpha[j]= \begin{cases} 0,&C_j\text{在左半含有被}\alpha\text{置真的文字},\\ 1,&\text{没有这样的文字}. \end{cases}

右侧 $b_\beta[j]$ 同理。若子句没有左半变量，则 $a_\alpha[j]=1$ ；这表示仍需右半负责，不能把它当作“空约束所以自动满足”。

任取一对赋值，拼成 $\sigma=\alpha\cup\beta$ 。子句 $C_j$ 是析取，所以它为假当且仅当左右两部分都没有真文字，即

\mathbf1\{C_j(\sigma)=0\}=a_\alpha[j]b_\beta[j].

对全部子句求和便得

a_\alpha\cdot b_\beta =\#\{j:C_j(\alpha\cup\beta)=0\}.

若 $F$ 有满足赋值，把它限制到两半，得到的每个坐标乘积都是0，故存在正交对。反过来，正交对的各乘积都是非负整数，总和为0迫使每个乘积为0；因而每条子句至少被一半满足，拼接赋值满足 $F$ 。索引保留了原部分赋值，所以找到一对向量后还能恢复见证。

左赋值00给出向量101；右赋值10给出010，各子句至少被一半满足且点积为零；换成右赋值00时第一条子句被两边同时遗漏，点积为一 — 每个共同的1是一条被违反的子句

例子与边界

四个变量、三个子句、全部十六对

取

F=(x_1\lor x_3)\land(\neg x_1\lor x_4) \land(x_2\lor\neg x_3\lor\neg x_4),

按 $(x_1,x_2)\mid(x_3,x_4)$ 分半，坐标次序就是显示的三个子句次序。

左赋值 $x_1x_2$	$a_\alpha$	右赋值 $x_3x_4$	$b_\beta$
$00$	$101$	$00$	$110$
$01$	$100$	$01$	$100$
$10$	$011$	$10$	$010$
$11$	$010$	$11$	$001$

例如左赋值00尚未满足第一、第三条，已由 $\neg x_1$ 满足第二条，故得到101。右赋值10已由 $x_3$ 满足第一条、由 $\neg x_4$ 满足第三条，故得到010。全部点积为：

左侧\右侧	$00$	$01$	$10$	$11$
$00$	$1$	$1$	$0$	$1$
$01$	$1$	$1$	$0$	$0$
$10$	$1$	$0$	$1$	$1$
$11$	$1$	$0$	$1$	$0$

六个零格恰对应六个满足赋值。例如 $101\cdot010=0$ 恢复 $0010$ ，三条子句分别由 $x_3,\neg x_1,\neg x_4$ 满足； $101\cdot110=1$ 对应0000，只有第一条为假。

编码边界

变量数为奇数时，两表长度可以不同，令 $N=2^{\lceil n/2\rceil}$ 就同时控制二者。若接口要求等长列表，可重复短表中的任意条目补齐，答案不变。不同赋值本来就可能产生相同向量；本页保留其列表索引，不能在无说明地去重后仍声称列表长度精确为 $2^{n/2}$ 。

空合取式（ $m=0$ ）恒真，对应零维向量的点积0；若含空子句，其坐标在两侧恒为1，所以不存在正交对，可以预先返回不可满足。 $n=0$ 时两表各含唯一的空赋值，也可直接处理。后面的渐近分析只需 $n\ge1$ 。

若误用模2点积，两条被违反的子句可能贡献 $1+1=0$ ，从而产生伪正交对。非负整数和的“为零当且仅当每项为零”是正确性证明真正使用的性质。

推论与应用

固定宽度下的指数预算

固定子句宽度 $k$ ，允许每条含至多 $k$ 个文字。先删除子句内重复文字、恒真的子句和重复的整条子句，并保留原变量全集。子句数因而满足

m\le\sum_{i=0}^k2^i\binom ni=O(n^k).

读取和规范化原始编码的费用为 $\operatorname{poly}(|F|)$ ；不能忽略读取任意多重复子句的成本。对每个部分赋值扫描所有子句并记录向量、索引，花费至多 $O(N(n+km))$ 时间。若假设OV算法的费用为 $O(N^{2-\varepsilon}(d+1)^c)$ ，其中 $c$ 是固定常数，则SAT总费用为

\operatorname{poly}(|F|)+O\!\left(N(n+km)+N^{2-\varepsilon}(m+1)^c\right).

因 $0<\varepsilon\le1$ ，枚举费用不会超过这个指数尺度； $k$ 固定时， $m$ 的贡献可吸收进多项式因子。又有

\begin{aligned} N^{2-\varepsilon} &=2^{(2-\varepsilon)\lceil n/2\rceil}\\ &\le2^{1-\varepsilon/2}\,2^{(1-\varepsilon/2)n}. \end{aligned}

奇数 $n$ 只增加常数因子。因此每个固定 $k$ 都得到 $O^*(2^{(1-\varepsilon/2)n})$ 算法；指数底数 $2^{1-\varepsilon/2}<2$ 的改进与 $k$ 无关，而被隐藏的多项式次数可以依赖 $k$ 。这正好否定SETH的量词顺序。

这里的目标实例对原SAT输入而言仍是指数大小；它是一项追踪运行时间的分半归约，不是把SAT多项式归约到一个容易问题后得到 $\mathrm P=\mathrm{NP}$ 。若目标改进只有 $N^2/\log N$ ，换回SAT也只得到 $2^n/\Theta(n)$ ，并没有跨过SETH所禁止的固定指数底数。

要求对数维度时，另付稀疏化成本

上面只由去重得到 $d=O(n^k)=O((\log N)^k)$ ，不能直接写成 $d=O(\log N)$ 。为得到后一种条件下界，假设存在一个固定 $\varepsilon>0$ ，对每个常数 $c\ge1$ ，都存在确定性OV算法 $A_c$ ，对 $d\le c\log_2N$ 的实例运行于 $O(N^{2-\varepsilon}\operatorname{poly}(d))$ 时间。可先把 $\varepsilon$ 缩小到至多1。

对任意固定SAT宽度 $k$ ，调用稀疏化引理，参数取 $\eta=\varepsilon/4$ 。它把原式写成至多 $2^{\eta n}$ 个 $k$ -CNF的析取，每个分支仍用原变量集，并有至多 $C(k,\eta)n$ 条子句。对每个分支做上述分半归约，则

d\le C(k,\eta)n\le2C(k,\eta)\log_2N.

取适用于 $c=\max\{1,2C(k,\eta)\}$ 的 $A_c$ ，并对所有分支的答案取析取。包括分支构造与列表枚举在内，总时间为

O^*\!\left(2^{\eta n}2^{(1-\varepsilon/2)n}\right) =O^*\!\left(2^{(1-\varepsilon/4)n}\right).

一般地，剩余指数改进是 $\varepsilon/2-\eta$ ，故必须先保证 $0<\eta<\varepsilon/2$ 。稀疏化不是免费的；把分支数省掉，就会高估归约保留下来的改进。

这里 $C,c,A_c$ 可以随固定 $k$ 变化，但同一个 $\varepsilon$ 要先于 $c$ 选定。若只有“每个 $c$ 存在某个越来越小的 $\varepsilon(c)>0$ ”，以上证明不再给出与 $k$ 无关的正改进。等价地，SETH推出：对每个固定改进幅度，都有某个对数维度常数使该改进无法实现。

列表索引还保护了这一规模论证。去重虽不改变OV是否有解，却可能大幅缩小实际列表长度；此时不能继续用原 $N$ 的等式，声称维度是去重后基数的对数。若必须用互异向量集合，可给左向量附加唯一编号位，并在右侧对应位填0；另用一个编号块给右向量编号、左侧填0。两个新块的交叉点积都为零，只增加 $2\lceil\log_2N\rceil$ 维，仍保留对数维度与原列表规模。

算法模型随归约一起传递

构造、列表生成和答案恢复都是确定性的，因此确定性OV算法才直接反驳本页所用的确定性SETH。若OV算法带随机错误，结论应改用相应随机化SETH并追踪多次调用的错误概率；不能借用当前假设的名称掩盖模型变化。

读完本页，应能从一个子句写出左右坐标，证明点积等于违反子句数，复算十六格表，并在 $N^{2-\varepsilon}$ 、分半取整和 $2^{\eta n}$ 三处费用之间保留正的指数改进。

参考资料

Ryan Williams, A New Algorithm for Optimal 2-Constraint Satisfaction and Its Implications, Theoretical Computer Science348(2–3), 2005, pp.357–365；作者公开稿§5.1、Theorem5.1，稿件pp.9–10，分半后的合作子集查询、指数传递及两个列表的OV定义。本文采用对称的未满足坐标，并写出取整与编码费用。
Virginia Vassilevska Williams, On Some Fine-Grained Questions in Algorithms and Complexity, ICM2018作者稿，§3、Theorem3.1，稿件pp.7–8：CNF到多组正交向量的坐标构造。本页只证明两组情形，并固定确定性假设。
Russell Impagliazzo, Ramamohan Paturi, Francis Zane, “Which Problems Have Strongly Exponential Complexity?”, Journal of Computer and System Sciences63(4), 2001, pp.512–530；§2、Corollary1，p.523：固定宽度SAT的至多 $2^{\eta n}$ 个线性子句分支。正文把该定理作为工具，并核算其指数成本，不复述其sunflower证明。

形式陈述 ​

每个坐标的语义与双向证明 ​

四个变量、三个子句、全部十六对 ​

编码边界 ​

固定宽度下的指数预算 ​

要求对数维度时，另付稀疏化成本 ​

算法模型随归约一起传递 ​

反向链接