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

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?

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.
• Consider this, if the Goldbach Conjecture is false. Given even $N$ > 2, is there NOT two primes that sum up to $N$? If the conjecture is false the output could be yes or no. – Dingle Berry Jun 21 '20 at 14:17