Set packing 问题是复杂性理论和组合数学中一个经典的NP完全问题,是卡普的二十一个NP-完全问题之一.给定一个有限集合 S 和一些 S 的子集,求问是否可以其中的 k 个子集,他们两两不相交. 形式化的定义:给定全集 ,和 的一组子集 .packing指一个集合 满足 且 中任意两个集合互不相交.定义 为packing的大小. 对于 set packing 的决定性问题,输入是 对和一个整数 ,求是否存在一个大小至少为 的 packing .对于 set packing 的决定性问题,输入是 对,求最大的 packing .