Kernelization（核化/核化预处理）：在参数化复杂性（Parameterized Complexity）中，一种多项式时间的预处理方法，把输入实例 \((I, k)\) 通过规则化简为一个更小的等价实例 \((I', k')\)，使其规模由仅依赖参数 \(k\) 的函数 \(f(k)\) 所界定（而与原始输入规模基本无关）。得到的小实例称为 kernel（核）。
（在不同语境下也可能指“核函数化”等别的含义，但计算机科学中最常见的是上述算法意义。）
/knlzen/
Kernelization can shrink a hard problem instance before running an exact algorithm.
核化可以在运行精确算法之前先把困难问题的实例缩小。
By applying kernelization rules, the researchers reduced the graph to a kernel whose size depends only on the parameter \(k\), enabling faster downstream computation.
通过应用核化规则，研究人员把图缩减为一个大小只依赖参数 \(k\) 的核，从而加速了后续计算。
该词由 kernel（核、核心） + -ization（……化的过程） 构成。这里的 kernel 指“保留问题本质难点后的核心实例”，kernelization 就是“把问题化简到核心规模”的过程。作为参数化算法领域的术语，它随相关理论体系的发展而固定下来。
Select Language