To prove NP, show an outline (pseudo-code okay) of the certifier algorithm and s
ID: 3823940 • Letter: T
Question
To prove NP, show an outline (pseudo-code okay) of the certifier algorithm and show that
(a) its running time is polynomial
(b) the token (i.e., certificate) size is bounded by a polynomial function of the Diverse-Set problem instance size.
To prove NP-hard, it would be easier to pick Independent-Set and reduce it to Diverse-Set. For this, provide the specific reduction mechanism and then show that (a) the reduction take polynomial time and (b) the Independent-Set problem instance has an independent set of size at most k if and only if the reduced Diverse-Set problem instance has a diverse set of size at most k.
Astore trying to analyze the behavior ofits customers will often maintain a two-dimensional array A, where the rows correspond to its customers and the to the it sells. entry Ali, jl specifies the quantity of product j that has been purchased by customer i. Here's a tiny example of such an array A. liquid detergent beer diapers cat litter Raj Alanis 2 Chelsea 0 One thing that a store might want to do with this data is thefollowing. Let us say that a subset s of the customers is diverse if no two of the product, at most one of the customer in s has ever bought it). A diverse set of customers can be useful, for example, as a target pool for market research. We can now define the Diverse Subset Problem as follows: Given an m x n array A as defined above, and a number k m, is there a subset of at least k of customers that is diverse? Show that Diverse Subset is NP-complete.Explanation / Answer
=> Diverse Subset Problem is NP: Given a set of k customers, it can be checked in polynomial time that no two customers in the set have
ever bought the same product.
=> Independent Set is known to be NP-complete.
=> Independent Set P Diverse Subset Problem: Suppose we have a black box for Diverse Subset Problem and want to solve an instance of Independent Set.
=> For our Independent Set Problem, we have a graph G=(V,E) and a number k, and need to find out if G contains an independent set of size
(at least) k.
=> We need to reduce the Independent Set Problem to a Diverse Subset Problem. We do this by constructing an array where each v in V is a
=> customer and each e in E is a product, and customer v purchased every product e for which the product edge e touches the customer node v.
=> Then we ask the black box for the Diverse Subset Problem if there is a subset of k customers that is diverse.
=> The black box for the Diverse Subset Problem will return “Yes” the Independent Set Problem is “Yes”, i.e. graph G contains an
independent set of size k.
=> The black box for the Diverse Subset Problem will return “Yes”: there is a subset of k customers that is diverse, no two customers in the subset have ever bought the same product. Then in the graph that can be constructed from this, no two customer nodes in the diverse subset share an edge, so it is an independent set of size k.
=> The Independent Set Problem is “Yes”, i.e. graph G contains an independent set of size k.
=> Then in the corresponding array, the independent set of size k corresponds to a set of customers where only one customer has purchased
each product, so there is a diverse subset of size k
=> Independent Set Problem requires polynomial time to construct the problem as a Diverse Subset Problem and polynomial calls to the Diverse
Subset Problem black box.
=> Hence, Independent Set P Diverse Subset Problem.
=> If Y is an NP-complete problem, and X is a problem in NP with the property that Y P X, then X is NP-complete.
=> Thus, Diverse Subset Problem is NP-complete.
(b) the Independent-Set problem instance has an independent set of size at most k if and only if the reduced Diverse-Set problem instance
has a diverse set of size at most k.
=> Efficient Recruiting is NP: Given a set of k counselors, it can be checked in polynomial time that at least one counselor is qualified in
each of the n sports.
=> Vertex Cover is known to be NP-complete Vertex Cover P Efficient Recruiting: Suppose we have a black box for Efficient Recruiting and want
to solve an instance of Vertex Cover.
=> For our Vertex Cover Problem, we have a graph G=(V,E) and a number k, and need to find out if G contains a vertex cover of size (at most) k.
=> We need to reduce the Vertex Cover Problem to an Efficient Recruiting Problem.
=> We do this by assigning each counselor to a node and each edge represents some sport.
=> Each counselor is qualified in the sports for which the sport edge is incident on their corresponding counselor node.
=> Then we ask the black box for the Efficient Recruiting Problem if there is a subset of k counselors that are qualified in all sports.
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.