Why is this NP complete? I am looking at the diverse subset problem in Kleinberg and Tardos, shown in the image: 



Why can't we give a polynomial time algorithm for this? Cant we iterate through each person a, and then each item i, and then see for each person b $\neq$ a if b has bought item i, then conclude that a and b cannot be diverse? And if we get through all items and no item that a has bought has been bought by b therefore implies they're diverse? Then we do this with each customer. What's wrong with this approach?
The algorithm you described isn't polynomial time because it has to consider every possible subset of customers (they are $2^m$ of these).

Solution

This problem is NP-hard because the vertex cover problem can be reduced to it.

https://en.wikipedia.org/wiki/Vertex_cover#Computational_problem

HINT: To do the reduction, consider how you would model $A$ as a graph and vice-versa. Once you've done that, consider how a "diverse set" is related to a vertex cover in the graphs.