CSE396-Assignment 7 Solved

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)∈S0

Note: 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 2.
Given 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.

 

Last update: April 30, 2020          Page 1 of 2 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.