[Solved] CSE396- Assignment 7

To help with this assignment, it would be best to read through chapter 7 alongside solving these problems, specifically the discussion of the time complexity classes P and NP. We have shifted the focus of our discussion from the types of problems that can be solved onto the types of problems can be solved within a given resource constraint (in our case, limited running time).Problem 1.Let the decision problem KNAPSACK be described as follows:KNAPSACK:INSTANCE: hS,W,Pi, such that S = {o1,o2,,ok} and W,P N, where each object oi is a pair oi = (wi,pi) for some wi,pi N.QUESTION: Is there a subset S0 S where P w W and P p P?(w,p)S0 (w,p)S0Note: The idea here is given a set of objects that have a weight and value associated with them, is there a subset of these objects that has a total value of P or more but has a total weight less than W?1(a) Provide one positive instance for KNAPSACK.1(b) Provide one negative instance for KNAPSACK.1(c) For your positive instance from 1(a), provide one valid certificate and one invalid certificate.1(d) Construct an algorithm that is a polynomial-time verifier for the KNAPSACK decision problem.Problem 2Given a graph G = (V,E), an independent set is a set S V such that v1,v2 S,(v1,v2) 6 E. Then we can define the problem of whether or not a graph contains an independent set of a particular size as follows:INDEPENDENT-SET:INSTANCE: hG,ki, where G is a graph and k N.QUESTION: Is there an independent set in G of size k?2(a) Provide one positive instance for INDEPENDENT-SET.2(b) Provide one negative instance for INDEPENDENT-SET.2(c) For your positive instance from 2(a), provide one valid certificate and one invalid certificate.2(d) Construct an algorithm that is a polynomial-time verifier for the INDEPENDENT-SET decision problem.Problem 3.For the following problem, reference the reduction from lecture showing that 3SAT pm SUBSET-SUM. This follows the same as the reduction in the book [theorem 7.56 proof, p320] except that hi should hold the digit 2 in the column for ci for each i {1,,k} and the digits of t corresponding to the each clause ci is 4 instead of 3.3(a) Compute the output generated by the reduction given the input(x1,x2,x3) = (x1 x2 x3)(x1 x2 x3).3(b) Using the result of the reduction in 3(a), generate a valid certificate for the output instance of SUBSETSUM. To do this, first identify a satisfying assignment to and then provide the corresponding certificate for the SUBSET-SUM instance.Problem 4.For the following problem, reference the reduction from lecture showing that 3SAT pm VERTEX-COVER. This follows the same as the reduction in the book [theorem 7.44 proof, p312].4(a) Compute the output generated by the reduction given the input(x1,x2,x3,x4) = (x1 x3 x4)(x1 x2 x4)(x1 x2 x4).4(b) Using the result of the reduction in 4(a), generate a valid certificate for the output instance of VERTEX-COVER. To do this, first identify a satisfying assignment to and then provide the corresponding certificate for the VERTEX-COVER instance.Problem 5. )Explain why membership of SUBSET-SUM or VERTEX-COVER in P would prove that P = NP.