核心化(kernelization),理学-计算机科学技术-计算机科学理论-算法-参数算法,主要用于解决难解问题的算法设计和分析技术。其目的并不是完全解决问题,而是试图减小原问题的规模,使得问题可以被更快地解决。核心化算法的输出是一个同样问题的更小实例,这个实例可以被看成是这个问题的“核心”难点。虽然有时候核心化算法可以解决问题,这个时候返回一个平凡的真或假的实例,但大多数情况下这不是期待的结果。核心化的想法由来已久,早期的工作被称为预处理,更多的是一个启发式的概念。预处理在计算中无所不在;譬如最著名的线性规划求解器CPLEX的巨大成功在很大程度上来自大量预处理技术。有时候,甚至最简单的预处理技术都能带来巨大的效果。但缺乏的是一个更好地理解它们的分析技术,或者说理论框架。这在传统的算法复杂性体系下是必然的结果,因为在最坏情况下总可以假定给定的实例已经是所有已知预处理规则都处理不了。注意如果一直可以压缩一个NP难问题的实例大小,那就隐含P=NP了,这被广泛认为是不可能的。参数计算(见参数算法)给核心化提供了一个系统的分析框架。