Consider the descriptions of the following problems: 1. Problem P_1: Given a set
ID: 3825699 • Letter: C
Question
Consider the descriptions of the following problems: 1. Problem P_1: Given a set S of positive integers {s_1, s_2, ..., s_n} and an integer C as input, is there a subset T of S such that the integers in T add up to C? 2. Problem P_2: Given a set S of positive integers {s_1, s_2, ..., s_n} as input, is there a subset T of S such that the integers in T add up to c_0? Here c_o is a positive integer constant. 3. Problem P_3: Given an undirected graph G and an integer K as input, is there a clique in G of size K? 4. Problem P_4: Given an undirected graph G as input does G contain a clique of size m? Here m is a positive integer constant. Now consider some additional propositions about the above problems (These may be TRUE or FALSE): 1. Proposition F_1: There is an algorithm A_1 that solves problem P_1 in O (nC) time. 2. Proposition F_2: There is an algorithm A_2 that solves problem P_2 in O(n) time. 3. Proposition F_3: P_3 is NP-complete. 4. Proposition F_4: There is an algorithm A_3 that solves problem P_4 in O(m^2n^m) time. Choose a correct statement from the choices below: If F_3 and F_4 are both TRUE, then P is not equal to NP. b) If F_1 and F_2 are both TRUE, P_1 is in P and P_2 is in P. F_1 must be FALSE. Such an algorithm A_1 cannot exist. d) If F_1 and F_2 are both TRUE, then P_2 is in P but we cannot conclude so about P_1.Explanation / Answer
a) F3 we know that its NP complete and if K is constant we can solve it in polynomial time
Hence A is the answer