经典SCP描述包含一个集合U以及U内元素构成的若干各小类集合S，目标是找到S 的一个子集，该子集满足所含元素包含了所有的元素且使小类集合个数最少。例如，U={1,2,3,4,5}，S={{1,2},{3,4},{2,4,5},{4,5}},找到集合能满足条件的可以有O={{1,2},{3,4}{4,5}}或是O={{1,2},{3,4},{2,4,5}}，至于具体选哪种组合，还有引申的一个问题：WSC，即Weighted Set Cover加权集合覆盖，每个集合类被赋予不同的权值，从而由权值决定最终的选择。

对于完全集合覆盖问题的决定版本是NPC（non-deterministic polynomial complete）的，而优化版本是NP-hard的

给定两个集合E和S，元素的集合E和E的子集的集合S，求出S的子集C，使得C中所有集合的并等于E，同时使得|C|最小。这就是经典的集合覆盖问题(SCP)。它是NP-hard类的最优化组合问题。对于NP-HARD类的问题，在P≠NP的假设下，是不存在多项式时间算法的，只能设计求解他们的近似算法或近似方案，或者对于问题条件进行限制使得限制后的子问题是一个非NP-HARD类的问题。集合覆盖问题在实际应用中有好多变型。若对于任意的s∈S有一个权重w(s)，并且同样求c，使得sum from s∈C w(s)最小。问题就成为了带有权重的集合覆盖问题。若对于任意s∈S有一个限制正整数k(s)，使得在s中的至多覆盖k(s)个元素，问题就成为带容量限制的集合覆盖问题(CSCP)，可以看出带权重或带容量限制的集合覆盖问题至少和集合覆盖问题一样难。Lang和Yannakanis证明了集合覆盖问题不存在c(lnn)，c<1/4的近似算法，除非NP(?)...