0
$\begingroup$

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?

$\endgroup$
2
1
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$ – Dingle Berry Jun 21 '20 at 14:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.