WebFlix maintains customer data in a 2D-array called WF. Where the rows correspond to the customers and the columns correspond to films that it rents. An entry WF[i,j] indicates the number of times a customer has rented a film.WebFlix wants to find subsets of customers who have never rented the same film. (i.e. they share no entries WF[i,j] ≥ 1). WebFlix calls these Distinct Customer Subsets. We define the Distinct Customer Subset problem as follows: Given a c by f (customers by films) array of customers and films and a number k ≤ c, is there a subset of at least k customers that is distinct?
Is the Distinct Customer Subset problem NP? Why or why not?
Is the Distinct Customer Subset problem NP-complete? If NP-complete show a polynomial-time reduction.