Is the complement of this decision problem in $P$?

Question

Are there any two primes that are NOT a factor of $M$ that multiply up to $M$?

Fact: Any two primes that multiply up to $M$. Must be factors of $M$!

Thus because of the fact above an $O(1)$ algorithm exists. It always outputs $NO$

Complement

Are there any two primes that are a factor of $M$ that multiply up to $M$?

Fact: A complement of a decision problem does not always require to always return $YES$ or $NO$. It can be either one!

(eg. $M$ = 6 and two primes that multiply up to $M$ are $3$,$2$.)

Well, this I find interesting this is deciding $Semi-Primes$.

Question

Shouldn't $Semi-Primes$ be in $P$, because what was shown above?

Answer 1

Careful how you come up with a complement. The original problem asks to satisfy the following, given M: $$\exists p,q: ((p\text{ and } q \text{ are prime})\land \neg(p\mid M)\land \neg(q\mid M) \land (pq=M))$$ As you say, the answer is always NO.

The complement of the problem should by definition have the opposite answer (YES) for ever $M$. To see why that's the case, negate the original problem (carefully): $$\neg\exists p,q: ((p\text{ and } q \text{ are prime})\land \neg(p\mid M)\land \neg(q\mid M) \land (pq=M))$$ Distributing through the $\exists$ gives: $$\forall p,q: \neg((p\text{ and } q \text{ are prime})\land \neg(p\mid M)\land \neg(q\mid M) \land (pq=M))$$ And distributing again makes this pretty trivial: $$\forall p,q: ((p\text{ or } q \text{ is not prime})\lor (p\mid M)\lor (q\mid M) \lor (pq\ne M))$$ So the complement is really asking: Given $M$, is it true that every pair of numbers $p$ and $q$ either has a non-prime or a divisor of $M$ or they don't multiply to $M$? It's a bit strange to claim this, but it's always true.