W 层级与 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；使用其他刻画时应给出等价定理来源，而非同时堆叠多个未连接模型。