The decision version of SEMIPRIME asks if a positive integer n can be factored into 2 primes.
The complement of SEMIPRIME asks if n cannot be factored into 2 primes.
My understanding is that the complement of SEMIPRIME is in NP because a certificate would consist of a list of k $\neq$ 2 primes whose product would be n.
To verify that the product is n would require k multiplications.
Since the input size is log(n), for the verification time to be polynomial in log(n) would require that k $= (log(n))^c$ for some constant c.
I don't understand how we would know that k $= (log(n))^c$?
Could someone clarify?
A natural number $n$ can always be represented with $log(n)$ bits. Each time you multiply a number by another number greater than 1, at least one more bit than either multiplicand is needed to represent the product. Therefore $log(n)$ multiplications are bound to produce a number $log(n)$ bits long or longer. So to produce $n$, $k$ < $log(n)$ always, leaving your verification process polynomial in duration.