The reduction is made from the -Hard problem 3SAT5 [Feige1996]. This is the classical 3SAT problem [Garey Johnson1979], but each variable appears in exactly 5 clauses. Using a well-known reduction [Garey Johnson1979], page 55, with an additional simple gadget, we can make a reduction from 3SAT5 to vertex cover (thus, independent set), obtaining a graph in which all vertices have degree either 5, or 0, and for which the largest independent set (for satisfiable instances of 3SAT5) has size , where is the number of vertices of . From this particular graph, we build a simple reduction to our problem of maximizing . Note that since we are searching for an oblivious hypothesis, the observations are not important (we can suppose that all examples have the same observation). That is why the reduction only builds class vectors (over classes), encoding the class membership of any of these identical observations. The idea is that the classes are in one-to-one mapping with the vertices, and there are two sets of class vectors built from :

- a set with vectors, encoding the vertices of . Each one is a class vector with only one ``1'' corresponding to the vertex, and the remaining components are zeroes. Each of the corresponding examples have weight .
- a set with vectors, where is the number of edges of . Each one encodes an edge, and therefore contains two ``1'' (and the remaining are zeroes) corresponding to the two vertices of the edge. Each of the corresponding examples have weight .

(23) | |||

(24) | |||

(25) |

Here, is the number of edges having their two vertices in the set corresponding to the values in , is the number of edges having their two vertices in the set corresponding to the values in , and is the number of edges having one of their vertices in the set, and the other one in the set. is the number of values in .

Suppose that (