跳到主要内容

子集之和问题

给定一组数 x1,,xkx_1,\cdots,x_k 和一个目标数 tt,定义子集之和问题

SUBSETSUM={S,tS={x1,,xk},{y1,,yl}{x1,,xk}, we have Σyi=t}SUBSET-SUM=\{\langle S,t\rangle|S=\{x_1,\cdots,x_k\},\exists \left\{y_{1}, \ldots, y_{l}\right\} \subseteq\left\{x_{1}, \ldots, x_{k}\right\} \text {, we have } \Sigma y_{i}=t\}

NP 完全复杂度类的。