形式陈述

参数化判定问题通常写成二元组 $(L,\kappa )$，其中 $L\subseteq {\mathrm{\Sigma }}^{\ast }$，而

$$\kappa :{\mathrm{\Sigma }}^{\ast }\to \mathbb{N}$$

是多项式时间可计算的参数化函数。等价地，也可把实例显式写成 $(x,k)\in Q\subseteq {\mathrm{\Sigma }}^{\ast }\times \mathbb{N}$。复杂度同时考察总输入长度 $n=|x|$ 与参数 $k$；同一个经典问题选取不同参数会得到不同的参数化问题。显式参数的编码长度仍应计入普通输入规模。

直觉

不把所有输入都视为同样困难，而是隔离一个希望在实际中较小的结构量，如解大小、树宽或编辑次数，并允许代价主要集中在它上面。

例子与边界

参数化顶点覆盖询问是否有大小至多 $k$ 的覆盖，以解大小为参数；暴力枚举 $n^k$ 虽对固定 $k$ 为多项式，却不是 FPT 形式。若改以 $n-k$、树宽或最大度为参数，复杂度可能完全不同。把 $k=n$ 这样的参数机械加入任何问题不会带来有用结构。

推论与应用

参数化框架组织 FPT、XP、W 层级、核化和有界搜索树。它尤其适合描述“总体规模大，但某个组合爆炸源较小”的算法，并能把预处理后的核大小作为可证明性能指标。

参考资料

• Rodney G. Downey and Michael R. Fellows, Fundamentals of Parameterized Complexity, Springer, 2013，Ch. 1, parameterized problems and parameterizations。
• Marek Cygan et al., Parameterized Algorithms, Springer, 2015，Ch. 1, parameterized complexity framework。