SubsetGCD is described by the following:

instance: A set of positive integers S and an integer k
question: does there exist a subset S′ of S of size k such that GCD(S′)=GCD(S)

Prove that SubsetGCD is np complete.

The hint for the problem is to reduce VertexCover to SubsetGCD

Question

SubsetGCD is described by the following:

instance: A set of positive integers S and an integer k 
question: does there exist a subset S′ of S of size k such that GCD(S′)=GCD(S)

Prove that SubsetGCD is np complete.

The hint for the problem is to reduce VertexCover to SubsetGCD

anonymous · Answer

I know what I'm supposed to do. Given an instance of VertexCover convert it into the form of SubsetGCD such that there exists a vertex cover of size k if and only if there exists a subset S′ of size k such that GCD(S′)=GCD(S)