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; I hope it'll attract a few more people by being less technical).