W-hierarchy

Definition / 定义

W-hierarchy（W 层级）：参数化复杂性理论中的一个分层体系，用来按“难度层次”分类一些固定参数不可解（通常被认为不太可能有高效参数算法）的参数化问题，常见层级包括 W[1]、W[2]、…。它用于与 FPT（固定参数可解） 等类别对比，帮助判断某个参数化问题是否可能存在高效算法。

Pronunciation / 发音（IPA）

/ˌdʌbəl.juː ˈhaɪəˌrɑːrki/

Examples / 例句

The problem is believed to be in the W-hierarchy.
这个问题被认为属于 W 层级中的某一类。

By designing a parameterized reduction, the authors place the task within the W-hierarchy of parameterized complexity.
通过构造参数化归约，作者将该任务定位到参数化复杂性中的 W 层级之内。

Etymology / 词源

这里的 W 源自参数化复杂性中对布尔电路结构的刻画（常与电路的“weft（纬度）/结构层次”这类概念相关），W-hierarchy 这一框架在 1990 年代由 Rod Downey 与 Michael Fellows 等学者系统化，用来把许多经典的组合问题按参数化难度分层整理（如 W[1]-hard、W[2]-complete 等）。

Related Words / 相关词

• Parameterized
• Complexity
• FPT
• Reduction
• Hardness
• Complete
• NP
• Circuit
• Weft

Notable Works / 文献作品中的出现

• Parameterized Complexity（Downey & Fellows, 1999）
• Fundamentals of Parameterized Complexity（Cygan, Fomin, Kowalik, Lokshtanov, Marx, Pilipczuk, Pilipczuk, Saurabh, 2015）
• Flum & Grohe 的参数化复杂性相关著作与综述中也会系统讨论 W-hierarchy（如 W[1]、W[2] 及其完备性结果）