2. Consider this problem: You are given positive integers a₁,...,an and k₁,..., kn, and a number

t where 0 ≤ t ≤n. Let c; be the value of the ki-th bit of the smallest prime factor of a;. De-

cide if there is a set SC [n] with size at least t, where the values of c; for each i S are all equal.

Prove that the above problem is in NP and co-NP. (Extra: Can you prove that the problem

is in P?)