2. Show that the following languages are in NP. (a) GRAD-FRIENDS = {((P), k) : P...

Transcribed Image Text:

2. Show that the following languages are in NP. (a) GRAD-FRIENDS = {((P), k) : P is a list of people where at least k are graduating seniors at the University of Michigan who are all Facebook friends with each other} To show that this language is in NP, you will have to verify that there are k seniors who are all Facebook friends. As a fellow student, you are given a list of seniors who will be graduating from the University of Michigan. You also have access to the internet and can find out which seniors are friends with each other on Facebook. (b) COMPOSITES = {n EN: n = pq for some integers p, q > 1} (c) 5-COLORING = {G = (V, E): G is 5-colorable}. Hint: A graph being 5-colorable means that given 5 distinct colors, we can color the vertices of the graph so that no two connected vertices share the same color. Recall the graph coloring problem in HW2. (d) Subset-Sum = {(A,T) : 3S C A such that s = T}. In other words, SUBSET-SUM is SES the set of pairs (A, T), where A is an array and T is an integer, such that there exists a set S that is a subset of A, and the sum of all the elements in S is T. 2. Show that the following languages are in NP. (a) GRAD-FRIENDS = {((P), k) : P is a list of people where at least k are graduating seniors at the University of Michigan who are all Facebook friends with each other} To show that this language is in NP, you will have to verify that there are k seniors who are all Facebook friends. As a fellow student, you are given a list of seniors who will be graduating from the University of Michigan. You also have access to the internet and can find out which seniors are friends with each other on Facebook. (b) COMPOSITES = {n EN: n = pq for some integers p, q > 1} (c) 5-COLORING = {G = (V, E): G is 5-colorable}. Hint: A graph being 5-colorable means that given 5 distinct colors, we can color the vertices of the graph so that no two connected vertices share the same color. Recall the graph coloring problem in HW2. (d) Subset-Sum = {(A,T) : 3S C A such that s = T}. In other words, SUBSET-SUM is SES the set of pairs (A, T), where A is an array and T is an integer, such that there exists a set S that is a subset of A, and the sum of all the elements in S is T.

Answer rating: 100% (QA)

The detailed answer for the above question is provided below optionC The way you show that anything ... View the full answer