Given a finite non-empty set $N$ of integers, call a subset $M$ of $N$ *good* if $gcd(M)=gcd(N)$. The other subsets are called *bad*.



> 
> Does there exist an algorithm which
>  computes a good subset of minimal size
>  in polynomial time (polynomial in $|N|$)?
> 
> 
> 


Using a greedy strategy, it is easy to find good subsets $M$ which are minimal with respect to inclusion (i.e. every proper subset of $M$ is bad). But it is not difficult to construct examples where such a greedy strategy may fail to find a set of globally minimal size.
Take for example N={6=2\*3, 10=2\*5, 15=3\*5, 1}. Then $gcd(N)=1$, and both {6,10,15} and {1} are good subsets. Both are minimal good subset wrt to inclusion. This can be easily generalized.


So, something more advanced would needed. Obviously, one can test all subsets, but then one gets exponential runtime. Is there a better way? Or can one prove that there isn't? Maybe this is equivalent to efficiently factoring primes?
As it is, I am not even sure whether this problem is in NP...


(Note that this question is about an important special case of an [earlier question of mine](https://mathoverflow.net/questions/44888/finding-globally-minimal-row-subsets-of-an-integer-matrix-which-generate-the-full); I hope it'll attract a few more people by being less technical).



Finding minimal subsets of a finite integer set with gcd equal to the whole set
I claim that the set cover problem (<http://en.wikipedia.org/wiki/Set_cover_problem>) can be reduced to this problem. So this problem is NP-hard.


Given a universe $U$ and a family $S$ that covers $U$, correspond the elements of $U$ to distinct primes and correspond each $A\in{}S$ to the product of the primes that correspond to the elements of $U-A$. Then a subcover of minimum size is equivalent to a good subset of minimum size.


