交叉合成（cross-composition）：计算复杂性理论（尤其是参数化复杂性与核化 kernelization）中的一种证明技术，用来把多个同类输入实例在多项式时间内“合成”为一个参数化实例，从而用于证明某些问题不太可能存在多项式核（polynomial kernel），除非出现被广泛认为不成立的复杂性塌缩（如 NP ⊆ coNP/poly）。
/ˌkrɔːs ˌkɒmpəˈzɪʃən/
/ˌkrɔs ˌkɑmpəˈzɪʃən/
Cross-composition is used to show that this problem likely has no polynomial kernel.
交叉合成常用于说明这个问题很可能不存在多项式核。
By designing a cross-composition from many SAT instances into a single parameterized instance, the authors derive a kernelization lower bound under standard complexity assumptions.
通过把多个 SAT 实例交叉合成为一个参数化实例，作者在常见的复杂性假设下推出了核化下界。
由 **cross-**（“交叉的、跨越多个的”）与 composition（“合成、组合”）构成，字面含义是“跨多个输入的合成”。在参数化复杂性语境中，它特指把许多实例“交叉”地编码进一个实例的构造方法。
Select Language