形式陈述
对参数化问题公理库参数化问题Parameterized problem实例与非负整数参数共同组成的判定问题。 ，核化算法在 上以 时间输出 ，满足
其中 是可计算函数。输出称为 kernel；若 是 的多项式，则称 polynomial kernel。标准 kernel 输出仍属于同一问题；允许输出到另一问题或任意短字符串时分别称 generalized kernel 或 compression，不能无标记混用。
对可判定参数化问题，存在某个可计算大小 kernel 当且仅当问题属于 FPT公理库参数化复杂度类 FPTFixed-parameter tractable · FPT可在 f(k)n^O(1) 时间内求解的参数化问题类。。反向方向：先多项式核化，再用任意判定算法解决大小至多 的有限核，后段成本只依赖 。正向方向：若 FPT 算法时间为 ，当 时可在 时间直接判定并输出固定 yes/no 实例；否则原实例自身大小已由 控制。该等价不保证 polynomial kernel。
直觉
核化把参数无关的冗余在正式求解前删掉，只留下由 控制的组合核心。每条化简规则都必须保持 yes/no 等价，所有规则结束后还需一个全局大小证明；“实验上变小”不是 kernel bound。
核化的等价缩减与参数界 预处理时间必须是总输入多项式，而不只是 。否则任何 FPT 求解器都可被重新命名为“预处理”，核化就失去独立意义。
例子与边界
参数化Vertex Cover公理库顶点覆盖Vertex cover与图中每条边至少一个端点相交、从而覆盖全部边的顶点子集。可用高次数规则得到 kernel。若顶点 的度大于 ，任何大小至多 的覆盖都必须含 ；否则需选择其超过 个邻居。于是删除 及其关联边，并把参数减一。
规则耗尽后最大度至多 。若仍有超过 条边，任意 个顶点最多覆盖 条边，可立即输出固定 no 实例；否则删除孤立点后非孤立顶点至多 。这给出等价性与大小界两个闭环，而非只列“删除高次数点”的步骤。
FPT 并不自动意味着 polynomial kernel；它只通过上述定理给某个可能增长极快的可计算 。反之，一个核很小也不代表实际求解容易，核上仍可能需要指数于 的精确算法。
推论与应用
核化是参数化预处理的形式语言，可用于顶点覆盖、反馈点集和各种删除问题。规则设计常结合强制选择、支配关系和局部替换，最终以参数函数界定剩余元素数。
Polynomial-kernel 下界需要 OR-composition、cross-composition 等额外复杂度工具；单凭 W[1]-hardness 不能得出“没有多项式核”。成员资格、FPT 时间与核大小是三种不同结论。
参考资料
- Marek Cygan et al., Parameterized Algorithms, Springer, 2015, Chs. 2–3.
- Rodney G. Downey and Michael R. Fellows, Fundamentals of Parameterized Complexity, Springer, 2013, Ch. 2.
