W 层级与 W[1]

形式陈述 ​

加权电路可满足性输入布尔电路公理库布尔电路Boolean circuit由逻辑门构成的有限无环有向图，计算布尔函数。 $C$ 与参数 $k$，询问是否存在恰有 $k$ 个输入位为 $1$ 的满足赋值。把 fan-in 超过某固定常数的门称为 large gate；电路的 weft 是任一输入到输出路径上 large gate 的最大数量。对固定 $t$，$W[t]$ 可由参数化问题经FPT 归约公理库FPT 归约FPT reduction · Parameterized reduction在 f(k)|x|^{O(1)} 时间内保持答案，并把目标参数限制为原参数函数的参数化 many-one 归约。到常数深度、weft 至多 $t$ 的加权电路可满足性来定义，不同教材会用规范化电路族给出等价版本。

已知包含链为

$$FPT\subseteq W[1]\subseteq W[2]\subseteq \cdots \subseteq W[P].$$

这些包含是否严格是开放问题。参数化 $k$-Clique 是 $W[1]$-complete；因此从它作 FPT 归约可证明目标 $W[1]$-hard，而目标再归约回某个 $W[1]$ 完全问题才给出成员资格。

直觉 ​

参数化问题公理库参数化问题Parameterized problem实例与非负整数参数共同组成的判定问题。常要求从许多对象中只选 $k$ 个。Weighted satisfiability 把“选了哪些对象”编码为恰有 $k$ 个真输入，weft 则衡量这些选择经过多少层大规模聚合才影响输出。W 层级提供的是参数化困难度证据，不是已证明的不可解边界。

$W[1]$-hard 通常被解释为“不太可能存在 $f(k)n^{O(1)}$ 算法”，其依据是普遍相信 $FPT\ne W[1]$；这个分离尚未证明，必须保留条件语气。

例子与边界 ​

对图 $G$，为每个顶点设输入位 $x_v$，要求赋值权重恰为 $k$。对每一对非边 $\{u,v\}$ 加约束 $\mathrm{\neg }{x}_u\vee \mathrm{\neg }{x}_v$，再对全部约束取 AND。电路接受当且仅当被选的 $k$ 个顶点两两相邻，即构成 clique；顶层大 AND 使路径 weft 为一，展示 $k$-Clique 如何进入 W[1] 的加权电路视角。

若把“恰有 $k$ 个 1”改成任意权重，参数结构会消失；普通 circuit SAT 与 weighted circuit SAT 的角色不同。大门阈值、深度常数和规范化门基也必须固定，不能凭图看起来只有两层就跳过正式模型。

XP 中的 $n^{f(k)}$ 算法对每个固定 $k$ 都是多项式，却不属于 FPT 所要求的 $f(k)n^c$ 形状。W[1]-hardness 针对后者，不等于排除所有固定参数下的多项式算法。

推论与应用 ​

W 层级组织 Clique、Dominating Set 等选择问题的参数化归约。证明目标 W[1]-hard 时，新参数必须由原 $k$ 的函数控制；把参数增长成 $n$ 会使困难性论证失效。

不同等价定义还包括短非确定计算与逻辑刻画。定义页以 weighted circuits 为主线，因为它显式展示 weft；使用其他刻画时应给出等价定理来源，而非同时堆叠多个未连接模型。

参考资料

• Jörg Flum and Martin Grohe, Parameterized Complexity Theory, Springer, 2006, Chs. 2–3.
• Rodney G. Downey and Michael R. Fellows, Fundamentals of Parameterized Complexity, Springer, 2013, Chs. 3–4.